Author Topic: FORMAL LANGUAGES AND AUTOMATA THEORY QUESTION PAPER  (Read 9896 times)

sams.raghu

  • dont know where to stay now
  • Senior Acumen
  • Hero Member
  • ***
  • Posts: 521
    • View Profile
    • Only ITAcumens
FORMAL LANGUAGES AND AUTOMATA THEORY QUESTION PAPER
« on: September 05, 2008, 05:28:14 pm »
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 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.

(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