My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
Download Model question papers & previous years question papers
|
Posted By: k vishaal Member Level: Gold Posted Date: 05 Sep 2008
|
2007 Jawaharlal Nehru Technological University Code No: R05310501 Set No. 1,III B.Tech I Semester Supplimentary Examinations, February 2008,FORMAL LANGUAGES AND AUTOMATA THEORY Question paper
Code No: R05310501 Set No. 1
III B.Tech I Semester Supplimentary Examinations, February 2008
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]
Figure 1b
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.
1 of 2
Code No: R05310501 Set No. 1
(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
? ? ? ? ?
2 o
Return to question paper search
|
|
|
Submit Previous Years University Question Papers and make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.
|
Watch TV Channels
|