10. The free abelian group of ranked with the standard set of free generator
is the lattice of integer co-ordinate prints of euclidean space R
d denoted
as 2
d is is
(a) triangular tessellation
(b) Torus
(c) Torus tessellation
(d) 2D-euclidean grid
THEORY OF COMPUTING
GROUP II
11. Draw the NFA that recognize the following set 01
* /00
* 1.
12. Construct a Turing machine that recognizes the set of all bit strings that
end with a ‘0’.
13. Derive the string aaabbbccc from S
ABSc S
Abc
→
→
,
, BA
AB
→
,
Bb bb Ab ab Aa aa
→
→
→
,
,
.
14. Is the Grammar ‘S
AB B
ab A aa A a B
b
→
→
→
→
→
,
,
,
,
’ ambiguous?
Prove.
15. Define Pushdown Automata.
16. What is a unit production & ε- (epsilon) production?
17. State the church’s Hypothesis.
18. State the Halting problem.
19. State some practical application for linear cellular automata.
20. Draw 3 examples for cayley graph.
THEORY OF COMPUTING
GROUP I
(ANSWER ALL QUESTIONS)
1. The grammar with the productions
S
aA bB B
b A
→
→
→
/ ,
,
ε (ε-epsi lon) belongs to
(a) Regular grammar only
(b) Context free grammar only
(c) Regular and Context free only
(d) Context sensitive only
2. State the regular expression recognized by the transition diagram
University Question Papers
325
A
B
0
Start
1
10
1
0
1
0