Saturday, 26 April 2014

FORMAL LANGUAGES AND AUTOMATA THEORY QUESTION PAPER

FORMAL LANGUAGES AND AUTOMATA THEORY QUESTION PAPER

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