Download Model question papers & previous years question papers
|
Posted By: cdteja Member Level: Silver Posted Date: 26 Nov 2007
|
2005 Jawaharlal Nehru Technological University jntu Question paper
|
|
|
Code No: NR310504 NR
III B.Tech I Semester Supplementary Examinations, November 2005
THEORY OF COMPUTATION
( Common to Computer Science & Engineering, Information Technology
and Computer Science & Systems Engineering)
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
? ? ? ? ?
1. (a) Let R={(1, 2), (2, 2), (2, 3)} be a relation on the set {1, 2, 3}, Find R*.
(b) Develop a Deterministic Finite Automation accepting the language given over
the alphabet {0, 1}. L = {the set of all strings such that every block of five
consecutive contain at least two o’s}
(c) Give mathematical definition of NFA and state main differences between NFA
and DFA. [4+8+4]
2. For the NFA- given check whether the string aannanan is accepted or not. If
accepted write the transition path. Find the equivalent NFA without epsilon tran-
sitions, explain the procedure used and check the string given on your new NFA.
Figure 1 [16 ]
Figure 1:
3. (a) Construct a regular expression representing the following sets The set of all
strings over {a, b} in which there are atleast two occurrences of b between any
two occurrences of a.
(b) Describe whether L = {a2n|n 1} is regular. State and explain the theorem
used. [8+8]
4. (a) Construct regular grammar G generating the regular set ab(a + b).
(b) Define CFG and give examples. What is CFL generated by the grammar
S ! abB, A ! aaBb,B ! bbAa,A ! E [8+8]
5. (a) Construct PDA for the grammar
S ! aA
A ! aABC/bB/a
B ! b
1 of 2
Code No: NR310504 NR
C ! c
(b) Convert the following to CNF
S ! 0S0/1S1/A
A ! 2B3
B ! 2B3/3. [8+8]
6. Construct Turing machine to accept following language and give its state transition
table and diagram. Check the machine by tracing a suitable instance.
L = { an bm: n 1 and n 6= m}. [16]
7. (a) Discuss different languages and their corresponding machines.
(b) Write the design procedure of shift reduce parser by taking a suitable example.
[8+8]
8. (a) Explain the Turing reducibility in detail.
(b) What is post correspondence problem? Is there any solution for the following
PCP problem? If so give the solution If not discuss why? [8+8]
List A List B
i wi xi
1 00 0
2 001 11
3 1000 011
? ? ? ? ?
2 of 2
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.