Theory of Computation - Online Test
Q1. Match the following:
Answer : Option C
Explaination / Solution:
Lemical Analyzer uses DFA to recognize the longest possible input sequence that makes up a
token. Parser takes input in the form of tokens and usually builds a data structure in the form
of parse tree. Here parse tree can be termed as a Production tree as parser uses production of
the grammar to check whether generated tokens form a meaningful compression).
Register allocation can be reduced to K-colouring problem where K is the number of registers
available on the target architecture.
Post order traversal of expression tree gives postfix notation for a given expression & this
post fix notation can be evaluated using stack.
Q2. Consider the following statements
I. The complement of every Turing decidable language is Turing decidable
II. There exists some language which is in NP but is not turing decidable
III. If L is a language in NP, L is turing decidable
Which of the above statements is/are true?
Answer : Option D
Explaination / Solution:
Turing decidable ⟶ Recursive language
Turing recognizable ⟶ Recursive enumerable language
I) Complement of turning decidable language is decidable which is true.
III) True ( Theorem )
Which violates (II) hence key is D
Q3. Consider the alphabet ∑ = {0.1},
the null/empty string λ and the sets of strings
X0 , X1 , and
X2 generated by the corresponding non-terminals of regular grammar. X0, X1, and X2 are
related as follows:
X0 = 1X1
X1 = 0X1 + 1X2
X2 = 0X1 + {λ}
Which one of the following choices precisely represents the strings in X0?
Answer : Option C
Explaination / Solution:
No Explaination.
Q4. Which of the following languages is/are regular?
Answer : Option A
Explaination / Solution:
Hence
m ≠ n, that mean n is greater than m, or m is greater than n.
So we need memory, so we can‟t draw DfA for it.
Q5. Which of the following languages is generated by the given grammar?
S → aS|bS|ε
Answer : Option D
Explaination / Solution:
Given grammar generates all strings of a’s and b’s including null string
∴ L = (a + b) *
Q6. Which of the following decision problems are undecidable?
I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = Φ?
II. Given a CFG G = (N, Σ, P, S) and a string x ∈ Σ∗, does x ∈ L(G)?
III. Given CFGs G1 and G2, is L(G1) = L(G2)?
IV. Given a TM M, is L(M) = Φ?
Answer : Option C
Explaination / Solution:
There is no known algorithm to check whether the language accepted by TM is empty.
Similarly there is no algorithm to check whether language CFG’s are equivalent.
Q7. Which one of the following regular expressions represents the language: the set of all binary
strings having two consecutive 0s and two consecutive 1s?
Answer : Option B
Explaination / Solution:
(a) contains 00 & 11 consecutively which is not the required condition.
(c) Doesn’t guaranty that both 00 & 11 will be present in the string.
(d) Says string should start with 11 & ends with 00 or vice versa.
Q8. Consider the following context-free grammars:
G1: S → aS|B, B → b|bB
G2: S → aA|bB, A → aA|B|ε , B → bB|ε
Which one of the following pairs of languages is generated by G1 and G2, respectively?
Answer : Option D
Explaination / Solution:
Lagrange’s generated by G1 = a*b+
Lagrange’s generated by G2 = a+b*\b+
Q9. Consider the transition diagram of a PDA given below with input alphabet Σ = {a, b} and
stack alphabet Γ = {X , Z}. Z is the initial stack symbol. Let L denote the language accepted
by the PDA.
Which one of the following is TRUE?
Answer : Option D
Explaination / Solution:
No Explaination.
Q10. Consider the following grammar.
What is FOLLOW (Q) ?
Answer : Option C
Explaination / Solution:
FOLLOW(Q) is FIRST(R) hence
FIRST(R) = {w, ϵ}
We add ‘w’ in FOLLOW(Q) and for ϵ we calculate FIRST(S)
FIRST(S) ={y}
FOLLOW(Q) is {w ,y}
