Theory of Computation - Online Test
Q1. Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent deterministic
Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and complementation
(4) Turing recognizable languages are closed under union and intersection.
Answer : Option C
Explaination / Solution:
(1) NTM ≅ DTM
(2) RELs are closed under union & but not complementation
(3) Turing decidable languages are recursive and recursive languages are closed under
intersection and complementation
(4) RELs are closed under union & intersection but not under complementation
Q2. What is the maximum number of reduce moves that can be taken by a bottom-up parser for a
grammar with no epsilon- and unit-production (i.e., of type A → ∈ and A → a) to parse a
string with n tokens?
Answer : Option B
Explaination / Solution:
To have maximum number of reduce moves, all the productions will be of the typeA→αβ
(where α and β could be terminals or non-terminals). Consider the following illustration
then:
Q3. Consider the languages L1 = Φ and L2 = {a} . Which one of the following represents L1 L2* UL1* ?
Answer : Option A
Explaination / Solution:
No Explaination.
Q4. Which of the following is/are undecidable?
1. G is a CFG. Is L (G) = Φ?
2. G is a CFG. IS L (G) = Σ*?
3. M is a Turning machine. Is L(M) regular?
4. A is a DFA and N is a NFA. Is L (A) = L (N) ?
Answer : Option D
Explaination / Solution:
There is an algorithm to check whether the given CFG is empty, finite or infinite and also to
convert NFA to DFA hence 1 and 4 are decidable
Q5. Consider the following two sets of LR(1) items of an LR(1) grammar
X → c.X, c / d X → c.X, $
X → .cX, c / d X → .cX, $
X → .d, c / d X → .d, $
Which of the following statements related to merging of the two sets in the corresponding
LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different
2. Can be merged but will result in S–R conflict
3. Can be merged but will result in R–R conflict
4. Cannot be merged since goto on c will lead to two different sets
Answer : Option D
Explaination / Solution:
1. Merging of two states depends on core part (production rule with dot operator), not on
look aheads.
2. The two states are not containing Reduce item ,So after merging, the merged state can not
contain any S-R conflict
3. As there is no Reduce item in any of the state, so can’t have R-R conflict.
4. Merging of stats does not depend on further goto on any terminal.
So all statements are false.
Q6. Consider the DFA given below.
Which of the following are FALSE?
1. Complement of L(A) is context–free
2. L(A) = L ((11*0+0)(0+1)*0*1*)
3. For the language accepted by A, A is the minimal DFA
4. A accepts all strings over {0, 1} of length at least 2
Answer : Option D
Explaination / Solution:
(1) L(A) is regular, its complement is also regular and if it is regular it is also context free.
(2) L(A) = (11*0+0)(0+1)*0*1* = 1*0(0+1)* Language has all strings where each string contains ‘0’.
(3) A is not minimal, it can be constructed with 2 states
(4) Language has all strings, where each string contains ‘0’. (atleast length one)
Q7. Consider the following languages
Which one of the following statements is FALSE?
Answer : Option D
Explaination / Solution:
Q8. Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ* . Which one of the following is TRUE?
Answer : Option C
Explaination / Solution:
2ε* is the power set of ε *
ε * is countabily infinite.
The power set of countabily infinite set is uncountable.
So 2ε* is uncountable, and ε * is countable
Q9. Which one of the following problems is undecidable?
Answer : Option A
Explaination / Solution:
There were algorithms to find the membership of CFG (using CYK algorithm) and finiteness
of CFG (using CNF graph) and emptiness. But there is no algorithm for ambiguity of CFG,
so it is undecidable.
Q10. 
Here wr is the reverse of the string w. Which of these languages are deterministic Contextfree
languages?
Consider the following languages over the alphabet Σ = {0,1,c}
Answer : Option C
Explaination / Solution:
For the languages L1 and L2 we can have deterministic push down automata, so they are
DCFL’s, but for L3 only non-deterministic PDA possible. So the language L3 is not a
deterministic CFL.
