LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

M.Sc. DEGREE EXAMINATION – MATHEMATICS

SECOND SEMESTER – APRIL 2012

MT 2960 – FORMAL LANGUAGES AND AUTOMATA

 

 

Date : 26-04-2012             Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

 

 

ANSWER ALL QUESTIONS

 

I a)  Construct a finite automation that accepts exactly those input strings of 0’s and1’s

that end in 111.

[OR]

1. b) Construct a DFA accepting all strings in (0 + 1)* having odd number of zeros.    (5)

 

 

1. c) i)Let L be a set accepted by a nondeterministic finite automation. Then prove

that there exists a deterministic finite automation that accepts L.

ii)Write a note on Epsilon-Closure and give an example.                                  (10+5)

[OR]

1. d) i)Let r be a regular expression. Then prove that there exists an NFA with

– transitions that accepts L(r).

1. ii) An NFA has moves.

Find an  equivalent DFA.                                                                                 (8+7)

 

 

II a)   Prove that L = { / n is an integer, n  1} is not regular.

[OR]

1. b) State and prove pumping lemma.                                                                         (5)

 

 

1. Minimize the following automation.

 

	0	1
A	B	C
B	D	E
C	F	G
D	D	E
E	F	G
*F	E	D
*G	G	F

[OR]

 

 

 

 

d)i) State and prove any three closure properties of regular languages.

1. ii) Construct an equivalent DFA for the following NFA

 

	a	b

(15)

 

III a)   Construct a grammar generating all palindromes over {0, 1}.

[OR]

1. b) Construct a grammar to generate L = { / n is an integer, n  1}        (5)

 

1. Write GNF grammar for for the following set of production rules

,

[OR]

1. d) Consider a grammar with production  rules

. The terminals

are Derive an equivalent grammar in CNF                         (15)

 

IV a)   Define a PDA and give an example.

[OR]

1. b) Construct a PDA that accepts {/ n  1} by empty stack                         (5)

 

1. c) If a PDA  A  accepts L by empty store then prove that there exists another PDA

B accepting L by final state.

[OR]

1. d) Let M be a PDA with    as  (q_0, 0,Z₀) = {( q_0, XZ₀)}, (q_0, 0,X) = {( q_0, XX)}

(q_0, 1,X) = {( q_1, )},  (q_1, 1,X) = {( q_1, )},  (q_1, ,X) = {( q_1, )},

(q_1,,Z₀) = {( q_1, )}. Construct a CFG generating  N(M).                      (15)

 

 

V a)  Design a  Turing Machine to add two positive integers.                      .

[OR]

1. b) Design a Turing Machine to compute .                               (5)

 

1. c)  Design a TM to accept the language L = { }

[OR]

1. d) Design a TM to perform proper subtraction. (15)

 

Go To Main page