COMPUTER SCIENCE AND ENGINEERING — FIFTH SEMESTER
THEORY OF COMPUTATIONS
Time: 3 Hours
Max. Marks: 50
*Answer All Ques tions
PART A
1. (a) Explain the Chomsky’s hierarchy of language.
(b) Explain the need for Theory of Computing.
2. (a) Prove by mathematical induction: Every integer, greater than 17, is
a nonnegative integer combination of 4 and 7. In other words, for
every n > 17, there exists integers i n and j n both ≥ 0, so that
n i
j
n
n
=
+
*
* .
4
7
(b) For every n
n n
≥
+
0
5
2
, (
) is divisible by 6.
3. (a) Prove that for every NDFA, there exists a DFA.
(b) Find the deterministic acceptor equivalent to
M
q q q
a b
= ({ , , }, ( , ), , , )
0 1 2
0
2
δ δ δ is given below:
State
a
b
q 0
q 0 , q 1
q 2
q 1
q 0
q 1
q 2
q 0 , q 1
4. (a) Find the language generated by the following grammars:
(i) S
A S
A
A S
→
→
0 1 0 1
1 1 1
| | | ,
| |
(ii) S
S A A
A
→
→
0 1 0 1
1 0 0
|
,
| .
(b) Construct a grammar to generate
{( ) |
) {( ) |
}.
ab n
ba n
n
n
≥ ∪
≥
1
1
5. List any 12 idetities for regular expressions.
6. Draw the transition system corresponding to (
) .
* *
ab c b
+
338
Theory of Automata, Formal Languages and Computation