THEORY OF COMPUTATION
Solutions
1. Number of trivial substrings in “GATE2013” are:
(a) 37 (b) 35
(c) 2 (d) 36
Solution: Option (c)
Explanation:
For any string, there will always be only 2 trivial substrings, ∈ and the given string itself.
2. Let the string be defined over symbols a and b then what will be the number of states in minimal
DFA, if every string starts and ends with different symbols?
(a) 5 (b) 4
(c) 3 (d) None
Solution: Option (a)
Explanation:
3. The total number of substrings present in “GATE” is:
(a) 7 (b) 10
(c) 11 (d) 8
Solution: Option (c)
Explanation:
1
𝐿 = {𝜀, 𝐺, 𝐴, 𝑇, 𝐸, 𝐺𝐴, 𝐴𝑇, 𝑇𝐸, 𝐺𝐴𝑇, 𝐴𝑇𝐸, 𝐺𝐴𝑇𝐸}
𝑛(𝑛+1)
Total number of substrings in a string of length n is +1
2
4. Let ∑= {a, b}, what are the number of states in minimal DFA, length of every string congruent
to mod 5.
(a) 2 (b) 3
(c) 5 (d) None
Solution: Option (c)
5. A minimal DFA that is equivalent to a NDFA has:
A. Always more states (b) Always less no. of states
C. Exactly 2n states (d) Sometimes more states
Solution: Option (d)
6. Consider following Regular Expression:
(i) a*b*b (a+ (ab)*)* b*
(ii) a*(ab + ba)* b*
What is length of shortest string which is in both (i) & (ii)?
(a) 2 (b) 3
(c) 4 (d) None
Solution: Option (d)
Explanation:
The shortest string is 𝜀 generated by both the regular expressions
7. S AB
A BB/ a
B AB/ b
Choose incorrect statement?
2
A. aabbb can be derived from above grammar
B. aabb can be derived from above grammar
C. ababab can be derived from above grammar
D. abbb can be derived from above grammar
Solution: Option (b)
Explanation:
Check each option by drawing a parse tree.
8. One of the following Regular Expressions is not the same as others. Which one?
(a) (a* + b*a*)* (b) (a*b* + b*a*)* (a*b*)*
(c) ((ab)* + a*)* (d) (a + b)* a*b*a*b*
Solution: Option (c)
Explanation:
abb cannot be generated by C, whereas it is generated by all other regular expressions.
9. The complement of CFL:
(a) Recursive (b) Recursive enumerated
(c) Not RE (d) The empty set
Solution: Option (a)
3
10. The language of primes in unary is:
(a) Regular (b) CFL
(c) DCFL (d) Context Sensitive
Solution: Option (d)
Explanation:
The language of primes in unary is {1𝑝 /𝑝 𝑖𝑠 𝑝𝑟𝑖𝑚𝑒}. Finite automata cannot recognize this
language as it has no memory. PDA also cannot recognize this as there is no pattern in the strings
that can be remembered using one stack. LBA can accept this, so it is a context sensitive language.
11. Consider the regular grammar generating the set of all strings ending with ‘00’, with terminals
{0,1} and non-terminals {S, A, B}, S being the initial state and B, the final state.
𝑆 1𝑆/ 0𝐴
𝐴 → 0𝐵
𝐵 → 0𝐵/1𝑆/0
The production missing is
(a) 𝐴 → 1𝑆 (b) 𝐵 → 𝜀
(c) 𝐴 → 1𝐵 (d) 𝑆 → 1𝐵
Solution: Option (a)
Explanation:
S → 1S | 0A
A → 1S | 0B
B → 1S | 0B | 0
4
12. What are the number of states needed in minimal DFA, that accepts (1+1111)*, with 1 as
alphabet.
(a) 5 (b) 4
(c) 1 (d) None
Solution: Option (c)
Explanation:
The language is 1*.
13. Consider the grammar:
SaSbS/ bSaS/ ε,
The smallest string for which the grammar has two derivation trees:
(a) abab (b) aabb
(c) bbaa (d) aaabbb
Solution: Option (a)
14. Consider the following languages:
L1= {anbn (n ≥ 0)}
L2= Complement (L1)
Choose appropriate options regarding languages L1 and L2
(a) L1& L2 are context free (b) L1 is CFL but L2 is RL
(c) L1 is CFL and L2 is CSL (d) None
Solution: Option (a)
Explanation:
𝐿1 is CFL and 𝐿2 = {𝑎𝑝 𝑏 𝑞 /𝑝 ≠ 𝑞 𝑎𝑛𝑑 𝑝, 𝑞 > 1} which is CFL.
15. The language L= { aNbN/ 0< N < 327th Prime number} is
(a) Regular (b) Not context sensitive
(c) Not recursive (d) None
5
Solution: Option (a)
Explanation:
Since this is finite language, it is regular.
16. Let ∑= {a}, assume language, L= {a2012.K/ K> 0}, what is minimum number of states
needed in a DFA to recognize L?
(a) 22012 + 1 (b) 2013
(c) 22013 (d) None
Solution: Option (b)
Explanation:
17. The following CFG,
S aB/ bA
A a/ aS/ bAA
B b/ bS/ aBB generates strings with
(a) Odd number of a's & odd number of b’s
(b) Even number of a's & even number of b's
(c) Equal number of a’s & b’s
(d) Odd number of a’s & even number of b’s
Solution: Option (c)
18. What type of grammar is this most accurately described as?
S b/aD
D a/aDD
(a) A regular grammar (b) CFG
(c) CSG (d) Type-0
6
Solution: Option (b)
Explanation:
(a) This cannot be regular because regular grammars are of the form 𝐴 → 𝑎, 𝐴 → 𝑎𝐵
(b) It is CFG because all the productions satisfy the constraints, they are of the form 𝐴 → 𝛾 where
𝛾 is a string of terminals and/or non-terminals.
(c) It can be CSG because all the productions are of the form 𝛼𝐴𝛽 → 𝛼𝛾𝛽, where 𝛼, 𝛽, 𝛾 are strings
of terminals and/or non-terminals.
(d) It can be Type – 0 or unrestricted grammar, because all productions are of the form 𝛼 → 𝛽 (no
restrictions).
But it can be most accurately described as CFG.
19. Consider the following NFA M over the alphabet {0,1}.
Let M1 be the NFA obtained by interchanging final and non-final states of M. Let the language
accepted by M be L and that accepted by M1 be L1. Choose correct statement:
(a) L1= L (b) L1∩ L2= Φ
(c) L1⊆ L2 (d) L1= (0+1)*
Solution: Option (d)
Explanation:
By interchanging final and non-final states, we get 𝐿1 = (0 + 1)∗ .
20. Let M= (Q, ∑, δ, S, F) and M’= (Q, ∑, δ, S, Q – F) where M accepts L and M’ accepts L1 and
M is NFA, what could be the relation between L and L’ ?
(a) L and L’ are complement to each other
(b) L and L’ are similar to each other
7
(c) L and L’ relation cannot be predicted
(d) None of the above
Solution: Option (c)
COMMON DATA QUESTIONS: Q.21, Q.22 AND Q.23, Q.24
21.
The DFA above accepts:
(a) The set of all strings containing two consecutive 1’s
(b) (0+1)*
(c) Set of all strings not containing two consecutive 1’s
(d) Set of all strings containing two consecutive 0’s
Solution: Option (b)
22. The minimal DFA of the above machine has:
(a) 1 State (b) 5 States
(c) 3 States (d) 2 States
Solution: Option (a)
Explanation:
Consider the grammar given below where the flowers are non-terminals and animals are terminals:
𝑋 → 𝑋𝑋/ 𝑎𝑋/ 𝑏𝑋/𝜀
where, a represents tiger and b represents lion, X represents Flowers.
23. The grammar generates
(a) twice as many tigers as lions (b) any number of tigers and lions
(c) more tigers than lions (d) unequal number of tigers and lions
Solution: Option (b)
8
24. The string for which the grammar has maximum of two derivation trees is:
(a) lion tiger lion (b) lion tiger
(c) tiger lion (d) None of the above
Solution: Option (d)
