NATIONAL OPEN UNIVERSITY OF NIGERIA
14/16 AHMADU BELLO WAY, VICTORIA ISLAND, LAGOS
SCHOOL OF SCIENCE AND TECHNOLOGY
MARCH/APRIL 2014 EXAMINATION
COURSE CODE: CIT 342
COURSE TITLE: FORMAL LANGUAGES AND AUTOMATA THEORY
TIME ALLOWED: 2½ HOURS
INSTRUCTION: ANSWER ANY FIVE (5) QUESTIONS. EACH QUESTION CARRIES 14 MARKS
1. (a) State and discuss four examples of analytic grammar formalisms (12 marks)
(b) What is a finite state automata? (2 marks)
2. (a) Formally define a PDA (4 marks)
(b) List and describe the types of PDAs (7 marks)
(c) List the three ways of defining a language (3 marks)
3. (a) List any four types of automata and state their respective recognizable language
(8 marks)
(b) In the context of automata theory, briefly describe the following terms: (6 marks)
i) Recognized language
ii) Run
iii) Transducer
4. (a) Within the context of computer science and formal language, Define the following terms
i) Alphabet (2 marks)
ii) String (2 marks)
(b) Write short notes on the Chomsky Hierarchy ( 4 marks)
(c) List and describe the two general types of string datatypes (6 marks)
5. (a) Distinguish between context-free grammar and regular grammar (4 marks)
(b) Distinguish between an alphabet and a language (3 marks)
(c) Enumerate any two of the typical questions asked about formalism in formal language
theory. (4 marks)
(d) Define automata theory. (3 marks)
6. (a) Distinguish between a word and a vocabulary in formal language. Use examples to
Illustrate your answer. (5 marks)
(b) Let V be a set of strings. Does V+ = V*? Justify your answer. (3 marks)
(c) Enumerate the components of formal grammar. (6 marks)
7. (a) State the Halting Problem. (2 marks)
(b) Enumerate the mathematical concepts needed to proof the Halting Problem. (6 marks)
(c) What does it mean to say a formally stated problem is: (6 marks)
i) Unsolvable?
ii) Provably unsolvable?
iii) Undecidable
You can get the exam summary answers for this course from 08039407882
Check the sample below
