Page 1 :
Code No: 155BK, JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD, , Time: 3 Hours, , 1.a), , b), , 2.a), b), , 3.a), b), , 4.a), b), , 5.a), , b), , 6.a), b), , , , , , , , R18, , , , B. Tech III Year I Semester Examinations, September - 2021, FORMAL LANGUAGES AND AUTOMATA THEORY, (Common to CSE, IT), Max. Marks: 75, Answer any five questions, All questions carry equal marks, , Convert the following. NFA to DFA, , , , , , , , , , , , , , , , , , State a b, Qo Q6 Q, Q Q {Qo,Qu}, Q Qo Q@, Qs" Q =, , , , , , Construct a DFA to accept the binary strings consisting of even number; of 0’s and odd, number of 1’s. [8+7], , Construct a DFA to accept the binary strings divisible by 5., , , , , , , , , , , , , , Eliminate the €-transactions of the following NFA. [7+8], State a b €, Q Q Q Q@, Qa Q Q Q, Q Q Q, Q3 Qo =, , , , , , , , , , , , Prove that Regular Languages are closed under i) Reverse ii) Union., , , , , , , , , , , , , , , , , , , , , , Identify the regular expression accepted by the following DFA. [7+8], , State a b, , Qo Q Q, , Q Qs. Q@, , Q Q Q, , Qs ~ —, , Prove that L={WW’/ W is a binary sting} is not regular language., Construct a DFA accepting language represented by (0+1)* (00+11) (0+1)*. [7+8], , Construct a PDA to accept the binary strings consists of number of 0’s.not equal to, number of 1’s., Construct a PDA to accept the language generated by the following CFG. [7+8], S>Aab, A>Aab|b, , Construct a PDA to accept the following language L= {a"b"/n>0}., , Construct a CFG to generate the binary strings consisting the number of 0’s is equal to, the twice the number of 1’s. [8+7], ex:-010;001010
Page 2 :
7.a), , b), , 8.a), , b), , Convert the following grammar into CNF., SaSa | bSb|a|b|aa| bb, , Simplify the following GFG, , S>aA|aBB, , A> Aaal€, , B>bB|bbC, , C>b, , [8+7], , Construct Turing Machine to accept following language and give its state Transition, , table and diagram. Check the machine by tracing a suitable instance:, : L={a'b'c" |n> I}., , Design-a‘TM whichrsubtracts two unary numbers. i.em-n-where m>=n:, , ---00000--, [7+8]
