CIT342 : FORMAL LANGUAGES AND AUTOMATA THEORY (2014)

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

For the 2015 – till date past questions for this course CLICK HERE

Contact me for your TMA, GST302 Business plan writeup, Project Writeup and also get your Exam Summary for this course.

Leave a Reply

MEET OVER 2000 NOUN STUDENTS HERE. 

Join us for latest NOUN UPDATES and Free TMA answers posted by students on our Telegram. 

OUR ONLINE TUTORIAL CLASS IS NOW ON!!! JOIN US NOW. 
JOIN NOW!
close-link