CIT3 342 MARCH/APRIL 2016 Examination

National Open University of Nigeria

14-16 Ahmadu Bello Way, Victoria Island Lagos 

  School of science and Technology

 MARCH/APRIL 2016 Examination

 

^{COURSE CODE: CIT3 342}

^{COURSE TITTLE: Formal Languages And Automata Theory}

 ^{TIME ALLOWED: 2hrs}

 Instructions: Answer any 5 questions. Each questions 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

*********************************************************************************
you can also attend Online Classes,Online Colleges,online tutorials. to be well prepared for exam Goodluck.