WHAT'S TRENDING

NOUN TMA Portal Login Page - National Open University of Nigeria TMA

Noun TMA Portal login Page link was more visible on the former noun student portal login website ( www.noun.edu.ng ) - if you could remembe...

NOUN Exam Past Questions - CIT 342 Formal Languages And Automata Theory MARCH/APRIL 2016 Examination

MARCH/APRIL 2016 Examination
COURSE CODE: CIT3 342
COURSE TITLE: Formal Languages And Automata Theory
TIME ALLOWED: 2hrs

Instructions: Answer any 5 questions. Each question carries 14 marks
1a. state Gödel incompleteness theorem 2marks
b. define context-sensitive grammars 2marks
c. write short note on decision problems 3marks
d. When is a formal system said to be:
i. Complete?
ii. Inconsistence? 2marks
e. Let V be a set of strings. Does V+=V*? justify your answer 3marks

2a. List any 4 types of automata and state their respective recognizable language
b. in the context of automata theory. Briefly describe the following terms
i. Recognized Language
ii. Run
iii. Transducer

3a. what is sentential form? 2marks
b. consider the linear grammar ({S,B.{a,b},S, {S—aS, S—B,B—bB,B---b}}) give any three sentential form of this grammar 3marks
c. List and describe the various components of a formal grammar 6marks
d what do you understand by the term automata theory? 3marks

4a. A non-deterministic finite automaton is not more powerful than a determine finite automaton. Discuss. 4marks
b. thinking of an automation as a computer, state the ways it can handle non-determinism? 3marks
c. state two of the ways of implementing a DFA 2marks
d. with respect to regular expressions, what is the precedence of the following operations relative to one another? 4marks
i. Kleene Star
ii. Concatenation
iii. Union

5a. Distinguish between context-free grammar and regular grammar 4marks
b. List the three ways of defining a language 4marks
c. formally define an automation 5marks

6a. Describe any three of the popular variation in the definitions of different components of Automata
b.What is/are the use(s) of Greibach Normal Form? 2marks

7a. state the formal definition of PDA 7marks
b. List and describe the types of PDAs. 4marks
c. Distinguish Between an alphabet and a language 3marks
SHARE

NOUN Portal Media

Teaching everything about Noun University, sharing all NOUN News & NOUNOnline Portal Guide to easy learning at the National Open University. See How to Apply for National Open University Admission. Study it, Process it and Share it.

  • Image
  • Image
  • Image
  • Image
  • Image
    Blogger Comment
    Facebook Comment

Post a Comment

I would like to learn how did this guide helped you. Share your valuable tips, and comments on the comment form.

P.S: It’s a pleasure to me if you share this guide with your relatives and friends on any social network. That will not only show me how much value you got from this guide but also how much you help others to learn about NOUN Portal

Here's What to Read Today

Recent Posts Widget