## November 25, 2011

### FORMAL LANGUAGES AND AUTOMATA THEORY JNTU previous years question papers

FORMAL LANGUAGES AND AUTOMATA THEORY JNTU previous years question papers

Time: 3 hours Max Marks: 80

All Questions carry equal marks

1. (a) Explain the differences between NFA and DFA.
(b) Design a DFA which accepts all strings which are ending with 101 over an Alphabet {0,1}. [8+8]

2. Construct DFA for given (figure 2) NFA with 2-moves. [16]

3. Give a regular expression for the set of all strings over {a, b} accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. [16]

4. (a) Obtain a Right Linear Grammar for the language
L = {anbm |n >= 2,m >= 3 }
(b) Obtain a Left Linear Grammar for the DFA as shown in figure 4b. [8+8]

5. (a) Reduce the Grammar G given by S!aAa
A!Sb/bcc/DaA
C!abb/DD
E!ac
into an equivalent grammar by removing useless symbols and useless productions from it.
(b) Convert the following grammar into CNF.
A!aB/bAB
B!b
D!d. [8+8]

6. (a) Let G be the grammar given by
S!aABB/aAA,
A!aBB/a,
B!bBB/A
Construct the PDA that accepts the language generated by this grammar G.
(b) Define Deterministic pushdown automata. Explain with an example. [8+8]

7. Give a Turing machine for the following:
(a) That computes ones complement of a binary number
(b) That shifts the input string, over the alphabet (0,1) by one position right by inserting ‘#'as the first character. [8+8]

8. (a) Explain about Deterministic context free language and Deterministic PDA.
(b) Show that L={anbncn : n >= 1} is a CSL. [8+8]