and 4 others joined a min ago.
0
2.6kviews
Automata theory and Computability Question Paper - Dec 18 - Computer Science (Semester 5) - Visvesvaraya Technological University (VTU)
1 Answer
0
38views
written 5.5 years ago by
shaikhainiya2001
• 0
|
Automata theory and Computability - Dec 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.
Note: Answer any FIVE full questions, choosing ONE full question from each module.
Module -1
1.a.i.
Define the following with example :
String
(2 marks)
00
1.a.ii.
Language
(2 marks)
00
1.a.iii.
Alphabet
(2 marks)
00
1.a.iv.
DFSM
(2 marks)
00
1.b.i.
$\mathrm{L}=\left\{\mathrm{W} \in\{0,1\}^{*} : \mathrm{W} \text { has } 001 \text { as a substring }\right\}$
(4 marks)
00
1.b.ii.
$\mathrm{L}=\left\{\mathrm{W} \in\{\mathrm{a}, \mathrm{b}\}^{*} : \mathrm{W} \text { has even number of a's and even number of } \mathrm{b}^{\prime} \mathrm{s}\right\}$
(4 marks)
00
OR
2.a.
Define NDFSM. Convert the following NDFSM to its equivalent DFSM.
(8 marks)
00
2.b.
Minimize the following DFSM.
(8 marks)
00
Module - 2
3.a.i.
Define Regular expression and write Regular expression for the following language.
$\mathrm{L}=\left\{\mathrm{a}^{2 \mathrm{n}} \mathrm{b}^{2 \mathrm{m}} | \mathrm{n} \geq 0, \mathrm{m} \geq 0\right\}$
(4 marks)
00
3.a.ii.
$\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{m}} | \mathrm{m} \geq 1, \mathrm{n} \geq \mathrm{I}, \mathrm{nm} \geq 3\right\}$
(4 marks)
00
3.b.
Obtain the Regular expression for the following FSM.
(8 marks)
00
OR
4.a.
i) Define a Regular grammar. Design regular grammars for the following languages.
(8 marks)
00
ii) Strings of a’s and b’s having strings without ending with ab.
iii) Strings of 0’s and 1’s with three consecutive 0’s.
4.b.
State and prove pumping theorem for regular languages.
(8 marks)
00
Module - 3
5.a.
i) $\mathrm{L}=\left\{0^{\mathrm{m}} 1^{\mathrm{m}} 2^{\mathrm{n}} | \mathrm{m} \geq 0, \mathrm{n} \geq 0\right\}$
(8 marks)
00
ii) $\mathrm{L}=\left\{\mathrm{a}^{\mathrm{i}} \mathrm{b}^{j} | \mathrm{i} \neq \mathrm{j}, \mathrm{i} \geq 0, \mathrm{j} \geq 0\right\}$
iii) $\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{n}-3} | \mathrm{n} \geq 3\right\}$
5.b.
Consider the grammar G with production.
(8 marks)
00
$\mathrm{S} \rightarrow \mathrm{AbB}$
$\mathrm{A} \rightarrow \mathrm{aA} | \in$
$\mathrm{B} \rightarrow \mathrm{aB}|\mathrm{bB}| \in$
Obtain leftmost derivation , rightmost derivation and parse tree for the string aaabab.
OR
6.a.
Define a PDA. Obtain a PDA to accept
(8 marks)
00
$\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{n}} | \mathrm{W} \in\{\mathrm{a}, \mathrm{b}\}^{*}\right\}$ . Draw the transition diagram
6.b.
Convert the following grammar into equivalent PDA.
(8 marks)
00
$\mathrm{S} \rightarrow \mathrm{a} \mathrm{ABC}$
$\mathrm{A} \rightarrow \mathrm{aB} | \mathrm{a}$
$\mathrm{B} \rightarrow \mathrm{bA} | \mathrm{b}$
$\mathrm{C} \rightarrow \mathrm{a}$
Module - 4
7.a.
State and prove pumping lemma for context free languages. Show that
(10 marks)
00
$\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{n}} \mathrm{c}^{\mathrm{n}} | \mathrm{n} \geq 0\right\}$ is not context free.
7.b.
Explain Turing machine model.
(6 marks)
00
OR
8.a.
Design a Turing machine to accept the language $\mathrm{L}=\left\{0^{\mathrm{n}} 1^{\mathrm{n}} 2^{\mathrm{n}} | \mathrm{n} \geq 1\right\}$ .
(8 marks)
00
8.b.
Design a Turing machine to accept strings of a’s and b’s ending with ab or ba.
(8 marks)
00
Module - 5
9.a.
Explain the following :
(6 marks)
00
i) Non deterministic Turing machine
ii) Multi– tape Turing machine.
9.b.
Define the following :
i) Recursively enumerable language
(6 marks)
00
ii) Decidable language
9.c.
What is Post correspondence problem?
(4 marks)
00
OR
10.a.
What is Halting problem of Turing machine?
(6 marks)
00
10.b.
Define the following :
(6 marks)
00
i) Quantum computer
ii) Class NP
10.c.
Explain Church Turing Thesis.
(4 marks)
00
ADD COMMENT
EDIT
Please log in to add an answer.