THEORY OF COMPUTING
GROUP II
11. Describe in English the sets accepted by the finite automata along with
the regular expression for the following transition diagram.
12. List the application of finte automata.
13. Show that the following context Free Grammar generates the language
of all strings over {0, 1} with twice as many 1’s as 0’s.
S
SS TT T T TT
T
S S S S
→
→
/
/
/
/
/ / .
0
0
0
1
1
1 1
14. Is the following grammar ambiguous. Justify
S
AB A aA
B
ab bB
→
→
→
,
/
/
/ .
ε
ε
15. Give the new set of productions after removng the unit productions for
the following CFG.
S
AA A B BB B
abB b bb
→
→
→
,
/ ,
/ / .
16. Construct two different NFA for the RE a
* .
17. Is unsolvability a halting problem. Justify.
18. When a ‘digraph’ becomes regular?
19. Define cellular automata.
20. What is meant by Recursively Enumerable language?
B.E. — COMPUTER SCIENCE & ENGINEERING — IV SEMESTER
THEORY OF COMPUTING
Time: 3 Hours
Max. Marks: 60
GROUP III
21. Construct and explain pushdown Automata for the following grammar.
S
aAA
A aS bS a
→
→
/ /
University Question Papers
327
A
B
0
Start
1
C
0
1
0
D
1
0
1