and 4 others joined a min ago.
0
1.3kviews
Automata theory and Computability Question Paper - Dec 17 - Computer Science (Semester 5) - Visvesvaraya Technological University (VTU)
1 Answer
0
8views
written 5.5 years ago by
shaikhainiya2001
• 0
|
Automata theory and Computability - Dec 17
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.
Module - 1
1.a.
Define the following terms with example : i) Alphabet ii) Power of an alphabet iii) Concentration iv) Languages
(4 marks)
00
1.b.
Draw a DFA to accept strings of a's and b's ending with 'bab'.
(3 marks)
00
1.c.
Convert the following NDFSM Fig. Q1 (c) to its equivalent DFSM.
(9 marks)
00
OR
2.a.
Draw a DFSM to accept the language,
(3 marks)
00
2.b.
Define distinguishable and indistinguishable states. Minimize the following DFSM,
(9 marks)
00
| S | 0 | I |
|---|---|---|
| A | B | A |
| B | A | C |
| C | D | B |
| *D | D | A |
| E | D | F |
| F | G | E |
| G | F | E |
| H | G | D |
i) Draw the table of distinguishable and indistinguishable state for the automata.
ii) Construct minimum state equivalent of automata.
2.c.
Write differences between DFA, NFA and $\mathrm{E}-\mathrm{NF} A$
(4 marks)
00
Module - 2
3.a.
Consider the DFA shown below:
(9 marks)
00
| States | 0 | 1 |
|---|---|---|
| $\rightarrow q_{1}$ | $q_{2}$ | $q_{1}$ |
| $q_{2}$ | $q_{3}$ | $q_{1}$ |
| *$q_{3}$ | $q_{3}$ | $q_{2}$ |
Obtain the regular expression $R_{i j}^{(0)}$ , $R_{i j}^{(1)}$ and simplify the regular expressions as much as possible.
3.b.
Give Regular expressions for the following languages on $\sum=\{a, b, c\}$
i) all strings containing exactly one a
(3 marks)
00
ii) all strings containing no more than 3 a's.
iii) all strings that contain at least one occurance of each symbol in $\sum$
3.c.
Let L be the language accepted by the following finite state machine.
(4 marks)
00
Indicate for each of the following regular expressions, whether it correctly describes L :
i) $(a \cup b a) b b^{*} a$
ii) $(\varepsilon \cup b) a\left(b b^{*} a\right)^{*}$
iii) ba $\cup a b^{*} a$
iv) $(a \cup b a)\left(b b^{*} a\right)^{+}$
OR
4.a.
Prove that the following language is not regular : L = ${0^{n} 1^{u} | n\gt0 \}$
(5 marks)
00
4.b.
If $\mathrm{L}_{1}$ and $\mathrm{L}_{2}$ are regular languages then prove that $\mathrm{L}_{1} \cup \mathrm{L}_{2}$ , $\mathbf{L}_{1}, \mathbf{L}_{2}$ and $\mathbf{L}_{1}^{*}$ are regular languages.
(5 marks)
00
4.c.
Is the following grammar is ambiguos?
(6marks)
00
$\mathrm{S} \rightarrow \mathrm{iC}+\mathrm{S}|\mathrm{iC}+\mathrm{SeS}| \mathrm{a}$
$\mathrm{C} \rightarrow \mathrm{b}$
Module - 3
5.a.
Define Grammar, Derivation, Sentential forms an d give one example for each.
(3 marks)
00
5.b.
What is CNF ? Obtain the folloeing grammar in CNF
(9 marks)
00
$\mathrm{S} \rightarrow \mathrm{ASB} | \varepsilon$
$\mathrm{A} \rightarrow \mathrm{aAS} | \mathrm{a}$
$\mathrm{B} \rightarrow \mathrm{SbS}|\mathrm{A}| \mathrm{bb}$
5.c.
Let G be the grammar,
(4 marks)
00
$\mathrm{S} \rightarrow \mathrm{aB} | \mathrm{bA}$
$\mathrm{A} \rightarrow \mathrm{a}|\mathrm{aS}| \mathrm{bAA}$
$\mathrm{B} \rightarrow \mathrm{b}|\mathrm{bS}| \mathrm{aBB}$
For the string aaabbbabbba find a
i) Left most derivation.
ii) Right most derivation
iii)Parse tree
OR
6.a.
Explain the following terms:
(3 marks)
00
i) Pushdown automata (PDA).
ii) Languages of a PDA.
iii) Instantaneus description of a PDA.
6.b.
Construct a PDA to accept the language
(10 marks)
00
Draw the graphical representation of this PDA. Show the moves made by this PDA for the string aabbaa.
6.c.
Convert the following CFG to PDA
(3 marks)
00
$S \rightarrow a A B B |$ aAA
$A \rightarrow a B B | a$
$B \rightarrow b B B | A$
$C \rightarrow a$
Module - 4
7.a.
If $L_{1}$ and $L_{2}$ are context free languages then prove that $\mathrm{L}_{1} \cup \mathrm{L}_{2}, \mathrm{L}_{1} \cdot \mathrm{L}_{2}$ and $\mathrm{L}_{1}^{*}$ are context free languages
(4 marks)
00
7.b.
Give a decision procedure to answer each of the following question:
(11 marks)
00
i) Given a regular expression $\alpha$ and a PDA $M$ , the language accepted by M a subject of the language generated by $\alpha$ ? ii) GIven a context-free Grammar G and two strings $\mathrm{S}_{1}$ and $\mathrm{S}_{2}$ , does G generate $\mathrm{S}_{1} \mathrm{S}_{2}$ ? iii) GIven a context free Grammar G, does G generate any even length strings. iv) Given a Regular Grammar G, is L(G) context-free ? \lt/div\gt \ltspan class='paper-ques-marks'\gt(12 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 Explain with neat diagram, the working of a Turning Machine model. \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 \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt8.b.\lt/b\gt Design a Turning machine to accept the language $L=\left{a^{a} b^{\prime} c^{k} | n>=1}right.$ . Draw the transition diagram. Show the moves made by this turing machine for the string aabbcc.
Module - 5
9.
Write short notes on :
(16 marks)
00
a. Multi-tape turing machine.
b. Non-deterministic turing machine.
c. Linear Bounded automata.
OR
10.
Write shrt notes on :
(16 marks)
00
a. Undecidable languages.
b. Halting problem of turing machine.
c. The post correspondence problem.
ADD COMMENT
EDIT
Please log in to add an answer.