(b) Find an equivalent FA and Regular expression from the given NFA
(Refer fig.)
22. (a) Design a PDA to recognize the language of all odd-length palindromes over {a, b}
(b) Construct CFG for the language generated in Question No. 22(a).
23. Construct GNF from the given grammar
S
aAa bBb
A c a
B
c b
C CDE
D
A B ab
→
→
→
→
→
|
|
|
|
|
| |
24. (a) Construct a Turing Machine that creates a copy of its input string
(Ex: abcd) to the right of the input but with a blank separating the
copy from the original.
(b) Design a Turing machine for computing the LCM of two numbers.
25. Write short notes on
(a) Cellular Automata
(b) Linear Cellular Automata
THEORY OF COMPUTING
Time: 3 hours
Max. Marks: 40
GROUP I
1. Find the start height of the following and draw the NFA for the given
regular expressions.
(a) ( ( /
) /
)
*
*
a a a aa aaa
(b) ((( /
) ) /
)
*
*
* *
a a aa aa
aaaaaa
2. Consider the two regular expressions
r1 0 1
: /
*
*
r2 01 10 1 0 0 1
:
/
/
/ ( )
*
*
*
* *
(a) Find a string corresponding to r1 but not to r2.
(b) Find a string corresponding to r2 but not to r1.
(c) Find a string corresponding to both r1 and r2.
(d) Find a string in {0, 1}
* corresponding to neither r1 nor r2.
3. Define and Construct a language for Context sensitive grammar.
‘We do not define ε-transitions for a Turing machine’. True or False.
Justify.
University Question Papers
333