and 2 others joined a min ago.
0
586views
Automata theory and Computability Question Paper - Jun 18 - Computer Science (Semester 5) - Visvesvaraya Technological University (VTU)
1 Answer
0
2views
written 6.9 years ago by
shadabkhan
• 20
|
Automata theory and Computability - Jun 18
Computer Science (Semester 5)
Total marks: 80
Total time: 3 Hours
INSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Draw neat diagrams wherever necessary.
1.a.
With a neat diagram, explain a hierarchy of language classes in automata theory.
(4 marks)
00
1.b.
Define determinisitic FSM. Draw a DFSM to accept decimal strings which are divisible by 3.
(6 marks)
00
1.c.
Convert the following NFDSM to its equivalent DFSM. (Refer Fig. Q. 1(c)).
(6 marks)
00
Also write transition table for DFSM.
OR
2.a.
Minimize the following finite automata, (Refer Fig. Q.2(A)).
(6 marks)
00
2.b.i.
Construct a mealy machine for a binary input sequence. Such that, if it has a substring 101, the machine outputs A. If input has substring 110, the machine outputs B. Otherwise is outputs C.
(3 marks)
00
2.b.ii.
Design a mealy machine that takes binary number as input and produce 2's complement of that number as output. Assume the string is read from LSB to MSB and end carry is discarded.
(3 marks)
00
2.c.
Convert the following mealy machine to Moore machine. (Refer Fig.Q.2(c)).
(5 marks)
00
Module - 2
3.a.
Define regular expression. Obtain a regular expression for the following languages :
(8 marks)
00
i) $\mathrm{L}=\left\{\mathrm{a}^{*} \mathrm{b}^{\mathrm{m}} | \mathrm{m}+\mathrm{n} \text { is even }\right\}$
ii) $\mathrm{L}=\left\{\mathrm{a}^{*} \mathrm{b}^{\prime \prime} | \mathrm{m} \geq 1, \mathrm{n} \geq 1, \mathrm{nm} \geq 3\right\}$
iii) $\mathrm{L}=\left\{\mathrm{w} :|\mathrm{w}| \mathrm{mod} 3=0 \text { where we }(\mathrm{a}, \mathrm{b})^{*}\right\}$
3.b.
Design an NDFSM that accept the language L(aa*(a+b)).
(4 marks)
00
3.c.
Convert the regular expression $(0+1)^{*} 1(0+1)$ to NDFSM.
(4 marks)
00
OR
4.a.
If the regular grammars define exactly the regular language, then prove that the class of languages that can be defined with regular grammars is exactly the regular languages.
(4 marks)
00
4.b.
Prove that the regular languages are closed under complement, intersection, difference, reverse and letter substitution.
(8 marks)
00
4.c.State and prove pumping theorem for regular language
TYPE_QUESTION_HERE
(4 marks)
00
Module - 3
5.a.
Define a context-free grammar. Obtain the grammar to generate the language
$\mathrm{L}=\left\{\mathrm{w} | \mathrm{n}_{\mathrm{a}}(\mathrm{w})=\mathrm{n}_{\mathrm{b}}(\mathrm{w})\right\}$
(4 marks)
00
5.b.
For the regular expression (011+1)(01) obtain the context free grammar.
(4 marks)
00
5.c.
What is ambiguity? Show that the following grammar is ambiguous.
(4 marks)
00
$S \rightarrow a B | b A$
$A \rightarrow a S |$ bAA $|$ a $B \rightarrow b S|a B B| b$ \lt/div\gt \ltspan class='paper-ques-marks'\gt(8 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt **OR** \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt6.a.\lt/b\gt Define PDA (Push Down Automata). Obtain a PDA to accept the language where WR is reverse of W by a final state. \lt/div\gt \ltspan class='paper-ques-marks'\gt(8 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt6.b.\lt/b\gt For the grammar \lt/div\gt \ltspan class='paper-ques-marks'\gt(4 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt6.c.\lt/b\gt Obtain a CFG for the PDA shown below: \lt/div\gt \ltspan class='paper-ques-marks'\gt(5 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt **Module - 4** \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt7.a.\lt/b\gt Consider the grammar $\mathrm{S} \rightarrow 0 \mathrm{A} | 1 \mathrm{B}$ $\wedge \rightarrow 0 \mathrm{AA}|1 \mathrm{S}| 1$ $\mathrm{B} \rightarrow 1 \mathrm{BB}|0 \mathrm{S}| 0$ Obtain the grammar in CNF. \lt/div\gt \ltspan class='paper-ques-marks'\gt(8 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt7.b.\lt/b\gt Show that $\mathrm{L}=\left{\mathrm{a}^{} \mathrm{b}^{} \mathrm{c}^{n} | \mathrm{n} \geq 0\right}$ is not context free. \lt/div\gt \ltspan class='paper-ques-marks'\gt(8 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt **OR** \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt8.a.\lt/b\gt With a neat diagram, explain the working of a basic Turing machine. \lt/div\gt \ltspan class='paper-ques-marks'\gt(4 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt8.b.\lt/b\gt Obtain a Turing machine to accept the language \lt/div\gt \ltspan class='paper-ques-marks'\gt(8 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt8.c.\lt/b\gt Briefly explain the techniques for TM construction. \lt/div\gt \ltspan class='paper-ques-marks'\gt(4 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt **Module - 5** \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt9.a.\lt/b\gt Obtain a Turing machine to recognize the language \lt/div\gt \ltspan class='paper-ques-marks'\gt(8 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt9.b.\lt/b\gt Prove that $\mathrm{HALT}_{\mathrm{rm}}={(\mathrm{M}, \mathrm{W}) |$ the Turing machine M halts on input W} is undecidable.
9.c.
With example, explain the quantum computation
(4 marks)
00
OR
10.a.
Write a short note on :
Multiple Turing machine.
(4 marks)
00
10.b.
Non deterministic Turing machine
(4 marks)
00
10.c.
The model of lnear bounded automation.
(4 marks)
00
10.d.
The post correspondence problem
(4 marks)
00
ADD COMMENT
EDIT
Please log in to add an answer.