KLE Dr. M.S.

Sheshgiri College of Engineering & Technology, Library, Belagavi

KLE Dr. M.S. Sheshgiri College of Engineering & Technology, Library, Belagavi
KLE Dr. M.S. Sheshgiri College of Engineering & Technology, Library, Belagavi
 15CS54

pm
USN
Fifth Semester B.E. Degree Examination, Dec.2018/Jan.2019

5
Automata Theory and Computability

7 :2
Time: 3 hrs. Max. Marks: 80

:4
Note: Answer any FIVE full questions, choosing ONE full question from each module.

G
12
2. Any revealing of identification, appeal to evaluator and /or equations written eg, 42+8 = 50, will be treated as malpractice.

-T
Module-1
1 a. Define the following with example :

9
i) String ii) Language iii) Alphabet iv) DFSM.

G
(08 Marks)

01
b. Design a DFSM to accept each of the following languages :

-T
i) L = {W  {0, 1}* : W has 001 as a substring}
-2
ii) L = {W  {a, b}* : W has even number of a’s and even number of b’s}. (08 Marks)
Important Note : 1. On completing your answers, compulsorily draw diagonal cross lines on the remaining blank pages.

G
01

-T
OR
7-

2 a. Define NDFSM. Convert the following NDFSM to its equivalent DFSM. (08 Marks)

G
-0

-T
U

b. Minimize the following DFSM. (08 Marks)

VT

m
-T

6p

G
G

:4

-T
-T

59

G
G

-T
12
-T

Module-2
G
19
G

3 a. Define Regular expression and write Regular expression for the following language.
-T

i) L = {a2n b2m | n ≥ 0 , m ≥ 0 }
-T

(08 Marks)
20

ii) L = {an bm | m ≥ 1 , n ≥ 1 , nm ≥ 3}.

G

b. Obtain the Regular expression for the following FSM. (08 Marks)
TG

1-

-T
-0

G
07

-T

OR
G

4 a. Define a Regular grammar. Design regular grammars for the following languages.
-T

i) Strings of a’s and b’s with at least one a.

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. (08 Marks)
G

b. State and prove pumping theorem for regular languages. (08 Marks)
-T

1 of 2
G
-T
TG
 15CS54

pm
Module-3

5
5 a. Define context free grammar. Design a context free grammar for the languages. (08 Marks)

:2
i) L = {0m 1m 2n | m ≥ 0 , n ≥ 0} ii) L = {ai bj | i ≠ j , i ≥ 0 , j ≥ 0}
iii) L = {an bn-3 | n ≥ 3}.

7
b. Consider the grammar G with production.

:4
S → AbB

G
12
A→ aA| (08 Marks)

-T
B → aB | bB | 
Obtain leftmost derivation , rightmost derivation and parse tree for the string aaabab.

G
01
OR

-T
6 a. Define a PDA. Obtain a PDA to accept
-2
L = {an bn | W  {a, b}*}. Draw the transition diagram. (08 Marks)

G
01
b. Convert the following grammar into equivalent PDA.

-T
S → aABC
7-

A→ aB|a (08 Marks)

B → bA|b
G
-0

C → a.
-T
U

Module-4
VT

7 a. State and prove pumping lemma for context free languages. Show that (10 Marks)
L = {an bn cn | n ≥ 0} is not context free. m
-T

6p
b. Explain Turing machine model. (06 Marks)

G
G

:4

OR -T
-T

8 a. Design a Turing machine to accept the language L = {0n 1n 2n | n ≥ 1}. (08 Marks)
59

b. Design a Turing machine to accept strings of a’s and b’s ending with ab or ba. (08 Marks)
G
G

-T
12

Module-5
-T

9 a. Explain the following :

i) Non deterministic Turing machine ii) Multi – tape Turing machine.
G

(06 Marks)
19
G

b. Define the following :

-T
-T

i) Recursively enumerable language ii) Decidable language. (06 Marks)

20

c. What is Post correspondence problem? (04 Marks)

G
TG

1-

-T

OR
10 a. What is Halting problem of Turing machine? (06 Marks)
-0

b. Define the following : i) Quantum computer ii) Class NP. (06 Marks)
G

c. Explain Church Turing Thesis.

07

(04 Marks)
-T
G

*****
-T
G
-T
G

2 of 2
-T
TG
KLE Dr. M.S. Sheshgiri College of Engineering & Technology, Library, Belagavi - 590008
KLE Dr. M.S. Sheshgiri College of Engineering & Technology, Library, Belagavi - 590008
KLE Dr. M.S. Sheshgiri College of Engineering & Technology, Library, Belagavi - 590008