THEORY OF COMPUTING
GROUP I
1. The regular expression for the set of strings that consists of alternating
0’s and 1’s.
(a) ( ) ( )
( )
( )
*
*
*
*
01
10
0 10
1 01
+
+
+
(b) ( ) ( ) ( ) ( )
*
*
*
*
01 10 1 01 0 10
(c) (
)( ) (
)
*
ε
ε
+
+
1 01
0
(d) both a & c.
2. Consider the following 2 DFA’s (Refer fig.)
3. The CFG is defined by the following productions
S
A B
A
A
B
B B
→
→
→
1
0
0 1
/
/
/
ε
ε
Which of the following substring is encountered during the derivation
process for the sentence 00101
(a) 0A1B (b) 0 1
∈ B (c) 0101B (d) All of the above
4. Match the following
1. BNF
(a) A xXyz
→
2. GNF
(b) A xy
→
3. CNF
(c) A
XxYyZz
→
(a) 1 - a, 2 - b, 3 - c
(b) 1 - b, 2 - c, 3 - a
(c) 1 - c, 2 - A, 3 - b
(d) 1 - a, 2 - b, 3 - c
5. The equivalent PDA for the given CFG is S
S A
→ 0 1 / (Refer fig.)
6. The pumping lemma for regular language
(a) xy z
′ for any i ≥ 0
(b) x yz
′ for any i ≥ 0
(c) xyz′ for any i ≥1
(d) x y z
′ ′ ′ for any i ≥1
7. The transition function of Turing machine can be defined as
(a) δ( , ) ( , , )
q x
p y D
=
(b) δ( , ) ( , , )
q
p y D
∈ =
(c) δ( , ) ( , , )
q xy
p y D
=
(d) No transistion function.
8. The Turing machine is said to be acceptance by halting, if
(a) δ( , )
q x is undefined
(b) δ( , )
q x is defined
(c) δ( , )
q x is ∈
(d) δ( , ) ( , )
q x
p y
=
9. ....................... model does not exchange information during
computation
(a) uniform arrays
(b) mosaic automata
(c) tessellation structure
(d) all of the above
10. The transition function of cellular space is denoted by
(a) δ:Q Q
Q
d
×
→
(b) δ:Q Q Q
d
× →
(c) δ:→ Q
d
(d) δ:Q
Q
d
→
University Question Papers
331