NATIONAL OPEN UNIVERSITY OF
NIGERIA CIT 342 Formal Languages
and Automata Theory
14/16, Ahmadu Bello Way, Victoria Island
Course Code: CIT 342
SCHOOL OF SCIENCE AND TECHNOLOGY October,
2013 Examination
Course Title: Formal Languages and Automata
Theory
Time: 2½ hrs
Credit Unit: 3
Instruction: Answer any five (5) questions. Each
question carries 14 marks
1.(a) Within the context of computer science and
formal language, Define the following term
(i)
Alphabet
(2 marks) (ii)
String
(2 marks)
(b) List and describe the general two types of
string datatypes (6
marks)
(c) What is the difference between Context -free
grammar and regular grammar (4 marks)
2.(a) State and discuss four examples of analytic
grammar formalisms include the following
(12 marks) (b) What is a finite state
automata?
(2 marks)
3.(a) List and describes the two types of
PDA (4
marks) (b) List seven things that define a PDA
Formally (7
marks) (c) State the differences between A
nondeterministic finite acceptor differs from a
deterministic
finite
acceptor
(3 marks)
4.(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
5.(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 for a formal
grammar. (6
marks)
6.(a) State the Halting
Problem.
(2marks) (b) Enumerate the mathematical
concepts needed to proof the Halting Problem
(c) What does it mean to say a formally stated
problem is: (6 marks)
(i) Unsolvable?
(ii) Provably unsolvable?
(iii) Undecidable?
7.(a) Formally define a PDA
(4 marks) (b) List and describe the types ofPDAs
(7 marks)
(c) List the three ways of defining a language (3 marks)