# Theory of Computation-3

CSE - Theory of Computation - Questions and solutions-3
Question:-
Option (A)
For token recognition in compilers, we should use regular grammar
Option (B)
For token recognition in compilers, we should use context free grammar
Option (C)
Syntactical constructs could be implemented with the help of regular grammars
Option (D)
None of these
Correct Option:
A
Question:-
Option (A)
L((ab)*)
Option (B)
L((aa)*)
Option (C)
L((a + b)*)
Option (D)
L((ba)*)
Correct Option:
D
Question Solution:
h((ab)*) can generate h(ab) = 0110  (00 + 1)*
h((aa)*) can generate h(aa) = 0101  (00 + 1)*
h((a + b)*) can generate h(a) = 01  (00 + 1)*
only h((ba)*) can generate (1001)*  (00 + 1)*
So correct answer is choice (d).
Question:-
Option (A)
strings containing “000” or “111” but not both
Option (B)
strings containing at least three 0’s or at least three 1’s but not both
Option (C)
strings containing at least three 0’s or at least three 1’s or both
Option (D)
strings containing “000” or “111” or both
Correct Option:
D
Question:-
Option (A)
(0 + 1)* 000111(0 + 1)* + (0 + 1)* 111000(0 + 1)*
Option (B)
(0 + 1)* 000(0 + 1)* + (0 + 1)* 111(0 + 1)*
Option (C)
(0 + 1)* 000(0 + 1)* 111(0 + 1)*
Option (D)
(0 + 1)* 000(0 + 1)* 111(0 + 1)* + (0 + 1)* 111(0 + 1)* 000(0 + 1)*
Correct Option:
D
Question Solution:
Either “000” precedes “111” or “111” precedes “000” in such a string.So, two parts are there in the regular expression to handle each case, as shown in choice (d)
Question:-
Option (A)
Decidable
Option (B)
Undecidable
Option (C)
Decidable if number of states in E is less than E'
Option (D)
None of these
Correct Option:
A
Question:-
Option (A)
The class of DFA’s, NFA’s and ∈-NFA’s are all equivalent
Option (B)
Every language that satisfies the pumping lemma for regular languages, is regular
Option (C)
If L is recognized by DFA M, then the language is recognize by the DFA , where is obtained from M by making all non-final states into final states and all final states into non-final states
Option (D)
If L is context free, then Ln is also context-free, for all n  0
Correct Option:
B
Question Solution:
Every regular language satisfies the pumping lemma for regular languages, but converse is not true