LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034
|
B.Sc. DEGREE EXAMINATION – MATHEMATICS
FIFTH SEMESTER – November 2008
MT 5404 – FORMAL LANGUAGES AND AUTOMATA
Date : 14-11-08 Dept. No. Max. : 100 Marks
Time : 9:00 – 12:00
PART-A
Answer ALL questions. (10 x2 = 20)
1) If T = {0,1} then write any four elements of T +.
2) Define a regular grammar.
3) Give an example for a context-free grammar.
4) Prove that every regular language context-free language .
5) Show that the family of PSL is closed under star.
6) Define a derivation tree.
7) Prove that G = is ambiguous.
8) Define a language accepted by a deterministic finite automation
9) Define a nondeterministic finite automation.
10) Construct a DFA accepting all strings in (0 + 1)* ending with 1.
PART-B
Answer ANY FIVE questions. (5 x 8 = 40)
11) Let G be a grammar with SAaS / SS/a , A SbA / SS /ba . For the string
aabbaaa find i) a leftmost derivation
- ii) a right most derivation
iii) a derivation tree
12) Write a note on Chomskian hierarchy.
13) Define concatenation of two languages. Also prove that the family of CSL is closed
under concatenation.
14) Write a CNF grammar for the language
15) Prove that is not a context free language.
16) Let G be a grammar with productions S S + S / SS / a / b .Find a
derivation tree for the string ab + ab
17) Construct a finite automation that accepts exactly those input strings of 0’s and1’s
that end in 101.
18) Construct a finite automation which can test wether a given positive integer is
divisible by 2.
PART-C
Answer ANY TWO questions (2 x 20 = 40 )
19) Let L be any context-free language. Prove that there exist constants p and q such
that if z is a word in L with then z can be written as where
such that for each integer is in L.
20) i) Write a note on Chomsky normal form.
- ii) Find a grammar in CNF grammar for the language
(8 + 12)
21) Let L =consisting of an equal number of a’s and b’s}.Write a CFG
to generate L
22) i) Write an ambiguous and unambiguous grammar for
- ii) Let L be a set accepted by a nondeterministic finite automation. Then prove
that there exists a deterministic finite automation that accepts L. (8 + 12)
Latest Govt Job & Exam Updates: