12. (a) Construct PDA from the given grammar.
S
S
S
S T S T T
T
T F T F F
F
S a
→
→ +
−
→
→
1
1
1
$
|
|
* | / |
( )|
(b) Show the moves of the PDA for accepting the sentence
a a a a
+ * / $
13. Design a Context Free grammar for Boolean expressions and Construct
PDA for the same.
THEORY OF COMPUTING
GROUP II
11. Describes in English the sets accepted by the finite automata along with
the regular expression for the following transition diagram.
12. List the application of finite 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 removing 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?
336
Theory of Automata, Formal Languages and Computation
A
B
0
Start
1
C
0
1
0
D
1
0
1