5. The Turing machine is computable if final state contains__________
(a) transition function
(b) halt state
(c) no transition function
(d) both b & c.
GROUP II
6. Check whether the following grammar is ambiguous or Unambiguous
S
S S
→ ( ) |ε
7. Rewrite the given grammar after removing unit production
S
AB
A B
B
aB Bb
→
→
→
| |ε
8. Define PDA
9. Find the moves for the following configuration of TM
Q 0
↓
0
1
1
Q 1
↓
0
1
1
10. Define Turing Machine.
GROUP III
Answer Any 2 Ques tions
11. Construct GNF for the BNF given in problem no. 7.
12. (a) Construct PDA from the following grammar
S
aAA bBB aB a
A aA a
B
bB b
→
→
→
|
| |
|
|
(b) Show the sequence of moves of PDA of problem given in 12(a).
13. Construct TM for identifying the language consisting of 0’s and 1’s in
which all the string consists of even no. of 0’s and 1’s.
330
Theory of Automata, Formal Languages and Computation