B.Tech I Semester Supplimentary Examinations, February 2008

2007 Jawaharlal Nehru Technological University

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 = {0m1n/m 0 and n 1} .

(b) Represent all five tuples for below transition (diagram 1b) and decide whether

it is DFA or NFA. [8+8]

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 0's.

(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 0's & odd number of

1's.

(d) The set of all strings over {0,1} in which the number of occurrences of is

divisible by 3. [4×4]

4. (a) Obtain a CFG to generate unequal number of a's and b's.

(b) Obtain a CFG to obtain balanced set of parentheses.(i.e every left parentheses

should match with the corresponding right parentheses). [2×8]

5. (a) What do you mean by ambiguity? Show that the grammar S ! S/S, S ! a is

ambiguous.

(b) Show that the grammar G with production

S ! a/aAb/abSb

A!aAAb/bS is ambiguous. [8+8]

6. (a) Explain the terms: Push Down Automata and context free language.

(b) Let G be a CFG with the following productions.

S ! a B c

A ! a b c

B ! a A b

C ! A B

C ! c

Construct a PDA M such that the language generated by M and G are equiv-

alent. [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) 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