NATIONAL OPEN UNIVERSITY OF NIGERIA

UNIVERSITY VILLAGE, PLOT 91, CASDASTRAL ZONE, NNAMDI AZIKIWE EXPRESS WAY, JABI, ABUJA.
FACULTY OF SCIENCES
MARCH 2018 EXAMINATION

Course Title:  CIT342: Formal Languages and Automata                                       Credit Unit: 3

Instruction:    Answer QuestionOne and any three others                                          Time: 3hrs

Question One

Q1a). Give the formal definition of the following:

i. FSA                       (2marks)

ii. DFA                      (2marks)

iii. NFA     (2marks)

Q1b) Briefly discuss the Chomsky hierarchy. What is the relationship among thevarious types of grammars described in the Chomsky hierarchy                 (10marks)

Q1c)Define the following terms:

i. Strings                   (2marks)

ii. Alphabets                            (2marks)

iii.Vocabulary         (2marks

Q1d) Define Turing Machines.          (3marks)

Question Two

Q2a)What you understand by unrestricted grammarsin Formal Language            (5marks)

Q2b) Briefly describe the following concepts:

1. semantics of a grammar        (5marks)
2. Automata theory   (5marks)

Question Three

Q3a) What is a pigeonhole?              (2marks)

Q3b) Describe an algorithm for the Operation of a DFA             (5marks)

Q3c) Briefly describe the pigeonhole principle. How is it related to them pumping lemma for regular languages?         (8marks)

Question Four

Q4a) Whatdo you understand by formal languages and Give any three examples of languages      (6marks)

Q4b) Is formal language finite or infinite? Discuss(4marks)

Q4c) State five what pumping lemma say. (5marks)

Question Five

Q5a)What do you understand by halting problem?(6marks)

Q5bDefine context-sensitive grammars(4marks)

Q5c) What do you understand by decision problems?. (5marks)

Question Six

Q6a)PDA is defined as a collection of seven things mention (7marks)

Q6bThe context-free languages are closed under the formation of?(3marks)

Q6c) State the two type of PDAs(5marks)