(b) Construct a Turing Machine that will accept the following langua -
ges in {a, b}
L a b n
n m
n m
=
≥
≠
{
,
,
}.
1
25. (a) Explain the basic properties of linear cellular Automata.
(b) Draw any 3 common types of Cayley graph.
THEORY OF COMPUTING
TEST II
Class: BE—CSE
Time 90 mts.
Sem: IV
Marks : 30
GROUP I
1. The CFG defined by ab
* is
(a) S
Sb a
→ |
(b)
S
XY
X
ax
Y
by
→
→
→
(c) C
SS baa abb
S
→
→
|
|
ε
(d) S
aS
S
Bs
→
→
2. Consider the Left Recursive (LR) grammar
S
Aa b
A
Ac bd
→
→
|
|
Which of the following grammar is equivalent to the given grammar.
When LR is removed
(a)
S
Aa b
A bdA
A cA
→
→
′
→ ′
|
|ε
(b) S
bA
A C da
→ ′
→ |
(c) S
Aa b
A CA
→
→ ′
|
(d) S
Aa b
A
A C bd
→
→ ′
|
| |ε
3. Match the following
1. BNF
(a) S
aAa A SbA
→
→
,
2. CNF
(b) S
aAA A bBB
→
→
,
3. GNF
(c) S
AA A a
→
→
,
(a) 1- a, 2 - b, 3 - c
(b) 1 - a, 2 - c, 3 - b
(c) 1 - b, 2 - c, 3 - a
(d) 1 - c, 2 - b, 3 - a
4. In PDA, the δ is defined by
(a) δ
γ
( , , ) ( , )
q a z
p
= 1 1
(b) δ
γ
( , ) ( , )
q z
p
= 1 1
(c) δ
γ
( , ) ( , )
q a
p
= 1 1
(d) both a & b.
University Question Papers
329