B.E. — COMPUTER SCIENCE & ENGINEERING
THEORY OF COMPUTING
SEMESTER IV
Time: 3 Hours
Maximum Marks : 60
GROUP II
11. Find a regular expression for the language of the set of all strings of 0’s
& 1’s whose number of 0’s is divisible by 5 and whose number of 1’s is
even.
12. Compute ∈-NFA for the following, regular expression
1 1 10
10 0 01
(
)
(
)
*
*
+
+
+
13. Prove that {
/
}
0 102
0
n
n n ≥ is not a regular language.
14. Find whether the given grammar is ambiguous (or) Unambiguous
S T U
T
aTbT c
U
aA aTbU
→
→
→
|
|
|
15. Rewrite the given grammar after removing unit production:
S
ABA
A aA
B
bB
→
→
∈
→
∈
|
|
16. Design a CFG generating the following language
{
/
}
a b c
j i k
i j k
≠ +
17. Define Turing Machine.
18. Why accepting state is called as Halting State in TM?
19. Differentiate Cellular and Linear Cellular automata.
20. Write the local rules of Cellular automata.
GROUP III
21. (a) Construct finite automata to recognize the language of all strings of
0’s and 1’s of length at least 1, if they were interrupted as binary
representation of integers, would represent integers evenly divisible by 3. Leading 0’s are permissible.
332
Theory of Automata, Formal Languages and Computation