Started by sams.raghu, Sep 05, 2008, 10:58 PM

previous topic - next topic
Go Down


B.Tech I Semester Supplimentary Examinations, February 2008

2007 Jawaharlal Nehru Technological University


(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
(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
(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

(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.
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
ITAcumens Forum with 2 lakhs post running for 7 years - Powered by HostGator Dedicated Server