Download Visvesvaraya Technological University (VTU) BE ( Bachelor of Engineering) CSE 2017 Scheme 2020 January Previous Question Paper 5th Sem 17CS54 Automata Theory and Computability
-
n(
CHiKOD
1
i f 17CS54
Fifth Semester B.E. Degree Examination, Dec.1 afi.2020
Automata Theory and Computability
Max. Marks: 100 Time: 3 hrs.
Note: Answer FIVE full questions, choosing ONE full question from each !nodule.
..,-
Module-1
1 a. Explain with example,
-. . ''
(i) Strings (ii) Language (iii) Function on string
71
-
.
b. Discuss standard operations on Languages with example.
co
-0
c. Construct DFSM for the following languages :
0
(i) L= iw E {a, b }* I 0) contains no more than one bl
(ii) L = {co E {a,b}* I 0) contains Even number of a's and odd number of b' s1
a==.
Give the transition Table and show that aabaa is accepted.
:-. -
-
If ,
OR
c
.
I
2 a. Convert the following e -NFSM to DFSM by eliminating E -transition.
0
1)
(06 Marks)
(04 Marks)
(10 Marks)
Fig. Q2 (a) (10 Marks)
b. Define distinguishable and indistinguishable states. Minimize the number of states in
DFSM.
7,1
6 0
0
B F
B G C
C A G
d.
-2
D C G
F
F G
G E
H G C
. ?
cN1
z
b.
0
E
(10 Marks)
Module-2
Define Regular expression. Write RE for the following :
(i)
Language of all strings of 0's and l's that have odd number of l's.
(ii) Language of all strings of 0's and l's that has at least one pair of consecutive 0's.
(iii) The Language of all strings of 0's and I 's that have no pair's of consecutive 0's.
(10 Marks)
Prove with an example that the class of language can be defined with regular Grammar is
exactly the regular language.
(10 Marks) .
FirstRanker.com - FirstRanker's Choice
LIBRAT
-
n(
CHiKOD
1
i f 17CS54
Fifth Semester B.E. Degree Examination, Dec.1 afi.2020
Automata Theory and Computability
Max. Marks: 100 Time: 3 hrs.
Note: Answer FIVE full questions, choosing ONE full question from each !nodule.
..,-
Module-1
1 a. Explain with example,
-. . ''
(i) Strings (ii) Language (iii) Function on string
71
-
.
b. Discuss standard operations on Languages with example.
co
-0
c. Construct DFSM for the following languages :
0
(i) L= iw E {a, b }* I 0) contains no more than one bl
(ii) L = {co E {a,b}* I 0) contains Even number of a's and odd number of b' s1
a==.
Give the transition Table and show that aabaa is accepted.
:-. -
-
If ,
OR
c
.
I
2 a. Convert the following e -NFSM to DFSM by eliminating E -transition.
0
1)
(06 Marks)
(04 Marks)
(10 Marks)
Fig. Q2 (a) (10 Marks)
b. Define distinguishable and indistinguishable states. Minimize the number of states in
DFSM.
7,1
6 0
0
B F
B G C
C A G
d.
-2
D C G
F
F G
G E
H G C
. ?
cN1
z
b.
0
E
(10 Marks)
Module-2
Define Regular expression. Write RE for the following :
(i)
Language of all strings of 0's and l's that have odd number of l's.
(ii) Language of all strings of 0's and l's that has at least one pair of consecutive 0's.
(iii) The Language of all strings of 0's and I 's that have no pair's of consecutive 0's.
(10 Marks)
Prove with an example that the class of language can be defined with regular Grammar is
exactly the regular language.
(10 Marks) .
17CS5
OR
4 a. Using Kleen's theorem, prove that any language that can be defined with a Regular
expression can be accepted by some FSM.
(10 Marks)
b.
State and prove pumping lemma for regular language and show that the language
L = {a" P is a prime number} is not regular. (10 Marks)
Module-3
5 a. Define context Free Grammar. Construct CFG for the following languages:
(i) Balanced parantheses.
(ii) L = {co E {a,b}
*
I co contains substring ab} and derive two strings for each language
along with parse tree. (10 Marks)
b. Explain deterministic PDA and construct DPDA for language given and give the trace for
the string abbaab and aababb.
L = lanbmamb" I m.n > 0 and n # ml. (10 Marks)
OR
6 a. Discuss Chomsky normal form and Greibach normal form. Convert the following Grammar
to Chomsky Normal form,
S --> aACa
b.
A?>Bla
B C
C ?> cCIE
Explain Non deterministic PDA and construct an NPDA for the language.
L = {ex& 10 e , b
Give the transition diagram and show the trace for a string abaaba.
(10 Marks)
(10 Marks)
Module-4
7 a. State pumping Lemma for context free language. (10 Marks)
b.
Define Turing Machine. Design TM to accept the language L = {a"b"cn I n 1}. Draw the
transition diagram and show the moves made by TM for the string aabbcc. (10 Marks)
OR
8 a. Explain with a neat diagram the working of TM and design a TM to accept all set of
palidrom over 10,1 Also show the transition diagram and instantaneous description on
string "10101". (14 Marks)
b. Discuss the relationship between the deterministic context free language and the languages
that are not inherently ambigus. (06 Marks)
Module-5
9 a. With a neat diagram, explain variants of Turing Machines.
b. Explain with example,
(i) Decidability (ii) Decidable languages (iii) Undecidable language.
OR
10 a. Discuss Halting problem and post correspondence problem with respect to TM.
b. Define non-deterministic TM and prove that there in a deterministic TM 'NV
T(M)= T (MO.
(10 Marks)
(10 Marks)
(10 Marks)
such that,
(10 Marks)
/ ? ' /
2 of 2
f',A, ?
cr?
FirstRanker.com - FirstRanker's Choice
This post was last modified on 02 March 2020