Download VTU BE 2020 Jan CSE Question Paper 15 Scheme 5th Sem 15CS54 Automata Theory and Computability

Download Visvesvaraya Technological University (VTU) BE ( Bachelor of Engineering) CSE 2015 Scheme 2020 January Previous Question Paper 5th Sem 15CS54 Automata Theory and Computability

15CS54
USN
C CO
c. 8
E >
o
Csi
z
C
Fifth Semester B.E. Degree Examination, Dee.2019/Jan.2020
Automata Theory and Computability
Time: 3 hrs. Max. Marks: 80
Note: Answer any FIVE full questions, choosing ONE full question from each module.
(04 Marks)
ii) L = {a, b}
*
: w does not contain substring aabl. (08 Marks)
c. Describe Machine based hierarchy of language classes. (04 Marks)
?
OR
2 a. For the following NDFSM, use ndfsmtodfsm to construct an equivalent DFSM. Begin by
showing the value of eps (q) for each state q : (08 Marks)
b. Let M be the following DFSM. Use minDFSM to minimize M. (08 Marks)
Module-2
a.

Define Regular Expression. Write regular expression for the following :
i) L = {w E {a, b}
*
: w does not end in ha}
ii) L = E 0 ? 9}
*
w corresponds to the decimal encoding, without leading 0's , of an
odd natural number} . (06 Marks)
b. Consider the FSM M. Use the fsmtoregexheuristic algorithm to construct a regular
expression that describes L(M). (05 Marks)
"6"
E.
Module-1
1 a. Briefly describe the applications of Theory of computation.
-0
b. Define DFSM. Build DFSM for the following languages.
i) L = E a, b} * : every a in w is immediately folloWed by b}
C.
g
}
oc
E
CC Tr
c ?
0
v
c
? o
? ?
2 a'
CJ v
73 8
o -
CO el
CO el
"
T
ff
d
.

0
..-
0) I.-
1
1 4
:
o
nY
?
174
?
ti?
?-?
1? a)
8 3
0
1 of 2
FirstRanker.com - FirstRanker's Choice
15CS54
USN
C CO
c. 8
E >
o
Csi
z
C
Fifth Semester B.E. Degree Examination, Dee.2019/Jan.2020
Automata Theory and Computability
Time: 3 hrs. Max. Marks: 80
Note: Answer any FIVE full questions, choosing ONE full question from each module.
(04 Marks)
ii) L = {a, b}
*
: w does not contain substring aabl. (08 Marks)
c. Describe Machine based hierarchy of language classes. (04 Marks)
?
OR
2 a. For the following NDFSM, use ndfsmtodfsm to construct an equivalent DFSM. Begin by
showing the value of eps (q) for each state q : (08 Marks)
b. Let M be the following DFSM. Use minDFSM to minimize M. (08 Marks)
Module-2
a.

Define Regular Expression. Write regular expression for the following :
i) L = {w E {a, b}
*
: w does not end in ha}
ii) L = E 0 ? 9}
*
w corresponds to the decimal encoding, without leading 0's , of an
odd natural number} . (06 Marks)
b. Consider the FSM M. Use the fsmtoregexheuristic algorithm to construct a regular
expression that describes L(M). (05 Marks)
"6"
E.
Module-1
1 a. Briefly describe the applications of Theory of computation.
-0
b. Define DFSM. Build DFSM for the following languages.
i) L = E a, b} * : every a in w is immediately folloWed by b}
C.
g
}
oc
E
CC Tr
c ?
0
v
c
? o
? ?
2 a'
CJ v
73 8
o -
CO el
CO el
"
T
ff
d
.

0
..-
0) I.-
1
1 4
:
o
nY
?
174
?
ti?
?-?
1? a)
8 3
0
1 of 2
4
-

A_
10 Write short notes on :
a. Undecidable languages.
b. Halting problem of TM.
c. Post correspondence problem.
d. Church ? Turing Thesis.
\-
I
S?
:"
?
?
?
?
c. Consider the FSM M. Use fsmtoregex algorithm to construct a regular expression that
describes L(M). (05 Marks)
OR
4 a. Show that regular languages are closed under complement and set difference. (06 Marks)
b. State and prove pumping lemma theorem for regular languages. And show that the language
L = {anbn: n > 0} is not regular. (10 Marks)
Module-3
5 a. Define CFG. Design CFG for the languages.
i) L= la
i
11
1
1 2i = 3j + 1) ii) L= Kr` l
n
l n? I). (08 Marks)
b. Define Chomskey Normal form. Convert the following CFG to CNF.
S/--> a ACa
?
A?aIB
B? ? C1c
C cCI E. (08 Marks)
OR
6 a. Define Ambiguity. Consider the grammar E + EE I * EE I - EE I x y. Find the leftmost,
rightmost derivations and parse trees for the string " + * - xyxy". (07 Marks)
b. Define PDA. Design a PDA to accept the following language.
L = {ww
R
: w e {a, b}
*
}. Draw the transition diagram for the constructed PDA. (09 Marks)
Module-4
7 a. Design a TM to accept the language L = {a" b
n
I n > 1 }. Obtain the transition table and
transition diagram. Also show the instantaneous description for the string "aabb". (11 Marks)
b. Explain the working principle of TM with diagram. (05 Marks)
OR
8 a. State and prove pumping theorem for CFL's shown that the language L = bn c" : n > 0} is
not context free. (10 Marks)
b. Explain the hierarchy within the class of CFL's (hierarchy of languages). (03 Marks)
c. Show that CFL's are closed under reverse. (03 Marks)
Module-5
9 a. Explain Multitape TM, with diagram. (05 Marks)
b. Prove that every language accepted by a multitape TM is acceptable by some standard TM.
(06 Marks)
c. Explain the model of Linear Bounded Automata. (05 Marks)
OR a,("JCIPt 'N\
Coq ?
'/ (16 Marks)
e-gc
2 of 2
? PP
FirstRanker.com - FirstRanker's Choice