Code No: R05310501

Set No. 1

III B.Tech I Semester Supplimentary Examinations, February 2008 FORMAL LANGUAGES AND AUTOMATA THEORY (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks 1. (a) Design a DFA for the following language. L = {0m 1n /m 0 and n 1} . (b) Represent all ve tuples for below transition (diagram 1b) and decide whether it is DFA or NFA. [8+8]

Figure 1b 2. (a) Design a Moore Machine to determine the residue mod 4 for each binary string treated as integer. (b) Design a Mealy machine that uses its state to remember the last symbol read and emits output y whenever current input matches to previous one, and emits n otherwise. [8+8] 3. Find a Regular expression corresponding to each of the following subsets over {0,1}*. (a) The set of all strings containing no three consecutive 0s. (b) The set of all strings where the 10th symbol from right end is a 1. (c) The set of all strings over {0,1} having even number of 0s & odd number of 1s. (d) The set of all strings over {0,1} in which the number of occurrences of is divisible by 3. [44] 4. (a) Obtain a CFG to generate unequal number of as and bs. (b) Obtain a CFG to obtain balanced set of parentheses.(i.e every left parentheses should match with the corresponding right parentheses). [28] 5. (a) What do you mean by ambiguity? Show that the grammar S S/S, S a is ambiguous.

1 of 2

Code No: R05310501 (b) Show that the grammar G with production S a/aAb/abSb AaAAb/bS is ambiguous.

Set No. 1
[8+8]

6. (a) Explain the terms: Push Down Automata and context free language. (b) Let G be a CFG with the following productions. SaBc Aabc BaAb CAB Cc Construct a PDA M such that the language generated by M and G are equivalent. [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 rst character. [8+8] 8. (a) What is decidability? Explain any two undecidable problems. (b) Show that the following post correspondence problem has a solution and give the solution. [8+8] I List A List B 1 11 11 2 100 001 3 111 11

2 of 2

Code No: R05310501

Set No. 2

III B.Tech I Semester Supplimentary Examinations, February 2008 FORMAL LANGUAGES AND AUTOMATA THEORY (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks 1. (a) Design a DFA that accepts the set{an }U {b/n 1} (b) Draw the transition diagram for below FA. M= { {A,B,C,D}, {0,1}, ,C, {A,C} } (A,0) = (A,1) = {A,B,C} (B,0) = B, (B,1) = { A, C } (C,0) = {B,C}, (C,1) ={ B, D } (D,0) = { A, B, C, D } (D,1) = {A}.

[10+6]

2. For the following NFA with -moves convert it in to an NFA with out -moves and show that NFA with -moves accepts the same language as shown in gure 2. [16]

Figure 2 3. Construct NFA for the following regular expressions (a) 0+10* +01*0 (b) (0+1)*(01+110). 4. (a) Obtain a CFG to generate unequal number of as and bs. (b) Obtain a CFG to obtain balanced set of parentheses.(i.e every left parentheses should match with the corresponding right parentheses). [28] 5. (a) Show that L = {ai bj /j = i2 } is not context free language. (b) List the properties of CFLs. (c) Find if the given grammar is nite or innite. SAB, ABC/a, BCC/b, Ca. 6. (a) Construct the PDA for the following grammar. SAA/a ASA/b 1 of 2 [8+5+3] [8+8]

Code No: R05310501 (b) Design a PDA for the following grammar. S0A A0AB/1 B1.

Set No. 2
[8+8]

7. (a) Design a Turing Machine that accepts the set of all even palindromes over {0,1}. (b) Given = {0,1}, design a Turing machine that accepts the language denoted by the regular expressions 00 . [8+8] 8. (a) Find whether the post correspondence problem P={(10,101),(011,11),(101,011)} has a match. Give the solution. (b) Explain Turing reducibility machines. (c) Show that if L and L? are recursively enumerable, and then L is recursive. [6+5+5]

2 of 2

Code No: R05310501

Set No. 3

III B.Tech I Semester Supplimentary Examinations, February 2008 FORMAL LANGUAGES AND AUTOMATA THEORY (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks 1. Construct DFA for the following: (a) L={w/w has both an even number of 0s and even number of 1s } (b) L= { w/w is in the form of x01y for some strings x and y consisting of 0s and 1s}. 2. (a) Design a Moore machine to determine the residue mod 5 for each ternary string (base 3 ) treated as ternary integer. (b) Convert the following Mealy machine into equivalent Moore machine as shown in gure 2b. [8+8] [28]

Figure 2b 3. Give the English description and NFA for the following regular expressions. (a) r=(1+01+001)*(+0+00) (b) r=[00+11+(01+10)(00+11)*(01+10)]* [8+8]

4. (a) Obtain a regular grammar to obtain the set of all strings not containing three consecutive 0 s. (b) Obtain a CFG to generate the set of all strings over alphabet {a ,b} with exactly twice as many as as bs. [28]

1 of 2

Code No: R05310501 5. (a) Simplify the grammar = { {S,A, B, C, E }, {a,b,c}, P, S } Where, P is S AB Aa Bb BC E c/

Set No. 3

(b) Prove that the following language is not context-free language L = {www |w {a, b} } is not context free. 6. Show that the languages (a) L1={0n 1m /n = m and n 1} (b) L2={0n 1m / n=2m and n 1} Are deterministic context free languages? 7. Give a Turing machine for the following: (a) That computes ones complement of a binary number

[8+8]

[8+8]

(b) That shifts the input string, over the alphabet (0,1) by one position right by inserting # as the rst character. [8+8] 8. (a) Find whether the post correspondence problem P={(10,101),(011,11),(101,011)} has a match. Give the solution. (b) Explain Turing reducibility machines. (c) Show that if L and L? are recursively enumerable, and then L is recursive. [6+5+5]

2 of 2

Code No: R05310501

Set No. 4

III B.Tech I Semester Supplimentary Examinations, February 2008 FORMAL LANGUAGES AND AUTOMATA THEORY (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks 1. (a) Explain the dierences 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 (gure 2) NFA with -moves. [16]

Figure 2 3. Give a regular expression for the set of all strings over {a, b} accepting all strings which have number of as divisible by 6 and number of bs divisible by 8. [16] 4. (a) Obtain a Right Linear Grammar for the language L = {an bm |n >= 2, m >= 3 } (b) Obtain a Left Linear Grammar for the DFA as shown in gure 4b. [28]

Figure 4b 5. (a) Reduce the Grammar G given by SaAa ASb/bcc/DaA Cabb/DD 1 of 2

Code No: R05310501

Set No. 4

Eac DaDA into an equivalent grammar by removing useless symbols and useless productions from it. (b) Convert the following grammar into CNF. SaAD AaB/bAB Bb Dd.

[8+8]

6. (a) Let G be the grammar given by SaABB/aAA, AaBB/a, BbBB/A Construct the PDA that accepts the language generated by this grammar G. (b) Dene Deterministic pushdown automata. Explain with an example. 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 rst character. [8+8] 8. (a) Explain about Deterministic context free language and Deterministic PDA. (b) Show that L={an bn cn : n >= 1} is a CSL. [8+8] [8+8]

2 of 2