# National Open University Exam Past Question – CIT342 JUNE/JULY EXAMINATION

## NATIONAL OPEN UNIVERSITY OF NIGERIA CIT342 Formal Languages and Automata Theory

14/16 AHMADU BELLO WAY, VICTORIA ISLAND, LAGOS SCHOOL OF SCIENCE AND TECHNOLOGY JUNE/JULY EXAMINATION

COURSE CODE:    CIT342

COURSE TITLE:  Formal Languages and Automata Theory

TIME ALLOWED: 2½ hrs

INSTRUCTION:    Answer any five (5) questions. Each question carries 14 marks

1a) A non-deterministic finite automaton is not more powerful than a deterministic finite automaton. Discuss. (4 marks)

1. b) Thinking of an automaton as a computer, state the way(s) it can handle non-determinism? (3 marks)
2. c) State two of the ways of implementing a D                                                               (2 marks)
3. d) With respect to regular expressions, what is the precedence of the following operations relative to one another? (4 marks)
4. i) Kleene Star
5. ii) Concatenation iii)  Union

2a) State the formal definition of a PDA.                                                                                     (7 marks) b) List and describe the types of PDAs.                                                                                        (4 marks) c) Distinguish between an alphabet and a language                                                                         (3 marks)

3a) Distinguish between context-free grammar and regular grammar                                             (4 marks)

1. b) List the three ways of defining a language (4½ marks)
2. c) Formally define an automaton (5½ marks)

4a) What is a sentential form?                                                                                                        (2 marks)

1. b) Consider the linear grammar: ({S, B}, {a, b}, S, {S →aS, S→B, B→bB, B→l}). Give any three
YOU MAY ALSO LIKE  National Open University Exam Past Question – EDA 844 MAY/JUNE 2012 EXAMINATION
 sentential form of this grammar (3 marks) c) List and describe the various components of a formal grammar. (6 marks) d) What do you understand by the term automata theory? (3 marks)

5a) State Godel incompleteness theorem                                                                                     (2 marks)

 b) Define context-sensitive grammars (2 marks) (3 marks) c) Write short note on decision problems? d) When is a formal system said to be: i) Complete? ii) Inconsistent? (2marks each) e) Let V be a set of strings. Does V+ = V*? Justify your answer. (3 marks)

6a) Describe any three of the popular variations in the definition of different components of automata.

1. b) What is/are the use(s) of Greibach Normal Form? (2 marks)

7a) List any four types of automata and state their respective recognizable language. b) In the context of automata theory, briefly describe the following terms:

1. Recognised language ii.      Run

iii.       Transducer

Close

Close