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

15CS54
USN
C CO
c. 8
E >

--- Content provided by FirstRanker.com ---

o
Csi
z
C
Fifth Semester B.E. Degree Examination, Dee.2019/Jan.2020

--- Content provided by FirstRanker.com ---

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}

--- Content provided by FirstRanker.com ---

*
: w does not contain substring aabl. (08 Marks)
c. Describe Machine based hierarchy of language classes. (04 Marks)
?
OR

--- Content provided by FirstRanker.com ---

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.

--- Content provided by FirstRanker.com ---

Define Regular Expression. Write regular expression for the following :
i) L = {w E {a, b}
*
: w does not end in ha}

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

expression that describes L(M). (05 Marks)
"6"
E.
Module-1
1 a. Briefly describe the applications of Theory of computation.

--- Content provided by FirstRanker.com ---

-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

--- Content provided by FirstRanker.com ---

}
oc
E
CC Tr
c ?

--- Content provided by FirstRanker.com ---

0
v
c
? o
? ?

--- Content provided by FirstRanker.com ---

2 a'
CJ v
73 8
o -
CO el

--- Content provided by FirstRanker.com ---

CO el
"
T
ff
d

--- Content provided by FirstRanker.com ---

.

0
..-
0) I.-

--- Content provided by FirstRanker.com ---

1
1 4
:
o
nY

--- Content provided by FirstRanker.com ---

?
174
?
ti?
?-?

--- Content provided by FirstRanker.com ---

1? a)
8 3
0
1 of 2
FirstRanker.com - FirstRanker's Choice

--- Content provided by FirstRanker.com ---

15CS54
USN
C CO
c. 8
E >

--- Content provided by FirstRanker.com ---

o
Csi
z
C
Fifth Semester B.E. Degree Examination, Dee.2019/Jan.2020

--- Content provided by FirstRanker.com ---

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}

--- Content provided by FirstRanker.com ---

*
: w does not contain substring aabl. (08 Marks)
c. Describe Machine based hierarchy of language classes. (04 Marks)
?
OR

--- Content provided by FirstRanker.com ---

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.

--- Content provided by FirstRanker.com ---

Define Regular Expression. Write regular expression for the following :
i) L = {w E {a, b}
*
: w does not end in ha}

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

expression that describes L(M). (05 Marks)
"6"
E.
Module-1
1 a. Briefly describe the applications of Theory of computation.

--- Content provided by FirstRanker.com ---

-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

--- Content provided by FirstRanker.com ---

}
oc
E
CC Tr
c ?

--- Content provided by FirstRanker.com ---

0
v
c
? o
? ?

--- Content provided by FirstRanker.com ---

2 a'
CJ v
73 8
o -
CO el

--- Content provided by FirstRanker.com ---

CO el
"
T
ff
d

--- Content provided by FirstRanker.com ---

.

0
..-
0) I.-

--- Content provided by FirstRanker.com ---

1
1 4
:
o
nY

--- Content provided by FirstRanker.com ---

?
174
?
ti?
?-?

--- Content provided by FirstRanker.com ---

1? a)
8 3
0
1 of 2
4

--- Content provided by FirstRanker.com ---

-

A_
10 Write short notes on :
a. Undecidable languages.

--- Content provided by FirstRanker.com ---

b. Halting problem of TM.
c. Post correspondence problem.
d. Church ? Turing Thesis.
\-
I

--- Content provided by FirstRanker.com ---

S?
:"
?
?
?

--- Content provided by FirstRanker.com ---

?
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)

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

i
11
1
1 2i = 3j + 1) ii) L= Kr` l
n

--- Content provided by FirstRanker.com ---

l n? I). (08 Marks)
b. Define Chomskey Normal form. Convert the following CFG to CNF.
S/--> a ACa
?
A?aIB

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

b. Define PDA. Design a PDA to accept the following language.
L = {ww
R
: w e {a, b}
*

--- Content provided by FirstRanker.com ---

}. 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

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

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.

--- Content provided by FirstRanker.com ---

(06 Marks)
c. Explain the model of Linear Bounded Automata. (05 Marks)
OR a,("JCIPt 'N\
Coq ?
'/ (16 Marks)

--- Content provided by FirstRanker.com ---

e-gc
2 of 2
? PP
FirstRanker.com - FirstRanker's Choice