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

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

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.

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

..,-
Module-1
1 a. Explain with example,
-. . ''
(i) Strings (ii) Language (iii) Function on string

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

71
-
.
b. Discuss standard operations on Languages with example.
co

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

-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

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

a==.
Give the transition Table and show that aabaa is accepted.
:-. -
-

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

If ,
OR
c
.
I

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

2 a. Convert the following e -NFSM to DFSM by eliminating E -transition.
0
1)
(06 Marks)
(04 Marks)

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

(10 Marks)
Fig. Q2 (a) (10 Marks)
b. Define distinguishable and indistinguishable states. Minimize the number of states in
DFSM.
7,1

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

6 0
0
B F
B G C

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

C A G
d.
-2

D C G

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

F
F G
G E
H G C
. ?

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

cN1
z
b.
0
E

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

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

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

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

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

(10 Marks) .
FirstRanker.com - FirstRanker's Choice
LIBRAT
-
n(

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

CHiKOD
1
i f 17CS54
Fifth Semester B.E. Degree Examination, Dec.1 afi.2020
Automata Theory and Computability

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

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,

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

-. . ''
(i) Strings (ii) Language (iii) Function on string
71
-
.

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

b. Discuss standard operations on Languages with example.
co
-0
c. Construct DFSM for the following languages :
0

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

(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.
:-. -

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

-

If ,
OR
c

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

.
I
2 a. Convert the following e -NFSM to DFSM by eliminating E -transition.
0
1)

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

(06 Marks)
(04 Marks)
(10 Marks)
Fig. Q2 (a) (10 Marks)
b. Define distinguishable and indistinguishable states. Minimize the number of states in

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

DFSM.
7,1

6 0
0

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

B F
B G C
C A G
d.
-2

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

D C G
F
F G
G E

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

H G C
. ?
cN1
z
b.

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

0
E
(10 Marks)
Module-2
Define Regular expression. Write RE for the following :

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

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

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

Prove with an example that the class of language can be defined with regular Grammar is
exactly the regular language.
(10 Marks) .
17CS5
OR

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

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

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

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}

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

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

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

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

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

b.
A?>Bla
B C
C ?> cCIE
Explain Non deterministic PDA and construct an NPDA for the language.

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

L = {ex& 10 e , b
Give the transition diagram and show the trace for a string abaaba.
(10 Marks)
(10 Marks)
Module-4

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

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

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

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)

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

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

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

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)

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

(10 Marks)
such that,
(10 Marks)
/ ? ' /
2 of 2

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

f',A, ?
cr?
FirstRanker.com - FirstRanker's Choice