FORMAL LANGUAGES AND AUTOMATA THEORY QUESTION PAPER

Started by sams.raghu, Sep 05, 2008, 05:28 pm

previous topic - next topic
Go Down

sams.raghu

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. [44]

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


Go Up
 

Quick Reply

With Quick-Reply you can write a post when viewing a topic without loading a new page. You can still use bulletin board code and smileys as you would in a normal post.

Warning: this topic has not been posted in for at least 120 days.
Unless you're sure you want to reply, please consider starting a new topic.

Note: this post will not display until it's been approved by a moderator.
Name:
Email:
Verification:
Please leave this box empty:

Type the letters shown in the picture
Listen to the letters / Request another image

Type the letters shown in the picture:

shortcuts: alt+s submit/post or alt+p preview