TheoryofComputation
Question 1 
A  50 
Question 2 
L_{1}=〈M〉M takes more than 2021 steps on all inputs
L_{2}=〈M〉M takes more than 2021 steps on some input
Which one of the following options is correct?
A  Both L_{1}and L_{2} are undecidable. 
B  L_{1}is undecidable and L_{2}is decidable. 
C  L_{1}is decidable and L_{2}is undecidable. 
D  Both L_{1}and L_{2} are decidable. 
L1 is decidable.
We can take all strings of length zero to length 2021.
If TM takes more than 2021 steps on above inputs then definitely it will take more than 2021 steps on all input greater than length 2021.
If TM takes less than 2021 steps:
In such a case suppose TM takes less than 2021 steps (let's say 2020 steps ) for string length 2021, 2022, 2023, then definitely TM will take 2020 steps for all input greater than 2023. Hence in both cases it is decidable.
Similarly L2 is also decidable. If we can decide for all inputs then we can decide for some inputs also.
Question 3 
A  2 
Option A accepts string “01111” which does not end with 011 hence wrong.
Option C accepts string “0111” which does not end with 011 hence wrong.
Option D accepts string “0110” which does not end with 011 hence wrong.
Option B is correct.
The NFA for language in which all strings ends with “011”
">Question 4 
A  L = { 
B  L = { 
C  L = { 
D  L = { 
Question 5 
A  L1. L2

B  L1 ∪ L2 
C  L1 ∩ L2 
D  L1 − L2 
L1. L2 => regular . CFL == CFL. CFL (as every regular is CFL so we can assume regular as CFL)
Since CFL is closed under concatenation so
CFL. CFL= CFL
Hence
Regular . CFL = CFL is true
L1 ∪ L2 => Regular ∪ CFL = CFL
Regular ∪ CFL = CFL ∪ CFL (as every regular is CFL so we can assume regular as CFL)
Since CFL is closed under union
Hence Regular ∪ CFL = CFL is true
L1 ∩ L2 => Regular ∩ CFL = CFL
Regular languages are closed under intersection with any language
I.e,
Regular ∩ L = L (where L is any language such as CFL, CSL etc)
Hence Regular ∩ CFL = CFL is true
Please note this is a special property of regular languages so we will not upgrade regular into CFL (as we did in S1 and S2). We can directly use these closure properties.
L1 − L2 => Regular − CFL = CFL
=> Regular − CFL = regular ∩ CFL (complement)
Since CFL is not closed under complement so complement of CFL may or may not be CFL
Hence Regular − CFL need not be CFL
For ex:
R= (a+b+c)* and L= {am bn ck  m ≠ n or n ≠ k} which is CFL.
The complement of L = {an bn cn  n>0} which is CSL but not CFL.
So
R − L = (a+b+c)* − {am bn ck  m ≠ n or n ≠ k}
=> (a+b+c)* ∩ L (complement)
=> (a+b+c)* ∩ {an bn cn  n>0}
=> {an bn cn  n>0}
Which is CSL. Hence Regular − CFL need not be CFL.
Question 6 
Which of the following conversions is not possible (algorithmically)?
A  Regular grammar to context free grammar 
B  Nondeterministic FSA to deterministic FSA 
C  Nondeterministic PDA to deterministic PDA 
D  Nondeterministic Turing machine to deterministic Turing machine 
Question 7 
Which of the following features cannot be captured by contextfree grammars?
A  Syntax of ifthenelse statements 
B  Syntax of recursive procedures 
C  Whether a variable has been declared before its use 
D  Variable names of arbitrary length 
Syntactic rules not checking the meaningful things such as if a variable is declared before it use (or) not.
Like this, things are handled by semantic analysis phase.
Question 8 
The regular expression for the language recognized by the finite state automaton of figure is __________
A  L = 0*1* 
L contains all binary strings where a 1 is not followed by a 0.
Question 9 
Every subset of a countable set is countable.
State whether the above statement is true or false with reason.
A  True 
B  False 
Question 10 
(a) Given a set
S = {x there is an xblock of 5's in the decimal expansion of π}
(Note: xblock is a maximal block of x successive 5’s)
Which of the following statements is true with respect to S? No reasons need to be given for the answer.
 (i) S is regular
(ii) S is recursively enumerable
(iii) S is not recursively enumerable
(iv) S is recursive
(b) Given that a language L_{1} is regular and that the language L_{1} ∪ L_{2} is regular, is the language L_{2} always regular? Prove your answer.
A  Theory Explanation. 
Question 11 
A grammar G is in ChomskyNormal Form (CNF) if all its productions are of the form A → BC or A → a, where A, B and C, are nonterminals and a is a terminal. Suppose G is a CFG in CNF and w is a string in L(G) of length, then how long is a derivation of w in G?
A  Theory Explanation. 
Question 12 
In some programming languages, an identifier is permitted to be a letter following by any number of letters or digits. If L and D denote the sets of letters and digits respectively, which of the following expressions defines an identifier?
A  (L ∪ D)^{+} 
B  L(L ∪ D)* 
C  (L⋅D)* 
D  L⋅(L⋅D)* 
L(L ∪ D)*
Question 13 
Consider a grammar with the following productions
S → a∝bb∝c aB S → ∝Sb S → ∝b bab S ∝ → bd bb
The above grammar is:
A  Context free 
B  Regular 
C  Context sensitive 
D  LR(k) 
Because LHS must be single nonterminal symbol.
S ∝→ b [violates CSG]
→ Length of RHS production must be atleast same as that of LHS.
Extra information is added to the state by redefining iteams to include a terminal symbol as second component in this type of grammar.
Ex: [A → αβa]
A → αβ is a production, a is a terminal (or) right end marker $, such an object is called LR(k).
So, answer is (D) i.e., LR(k).
Question 14 
Which of the following definitions below generates the same language as L, where L = {x^{n}y^{n} such that n >= 1}?
I. E → xEyxy II. xy(x^{+}xyy^{+}) III. x^{+}y^{+}
A  I only 
B  I and II 
C  II and III 
D  II only 
Question 15 
A finite state machine with the following state table has a single input x and a single out z.
If the initial state is unknown, then the shortest input sequence to reach the final state C is:
A  01 
B  10 
C  101 
D  110 
If A is the start state, shortest sequence is 10 'or' 00 to reach C.
If B is the start state, shortest sequence is 0 to reach C.
If C is the start state, shortest sequence is 10 or 00 to reach C.
If D is the start state, shortest sequence is 0 to reach C.
∴ (B) is correct.
Question 16 
Let Σ = {0,1}, L = Σ* and R = {0^{n}1^{n} such that n >0} then the languages L ∪ R and R are respectively
A  regular, regular 
B  not regular, regular 
C  regular, not regular 
D  not regular, no regular 
Question 17 
Let L be a language over ∑ i.e., *L ≤ ∑ . Suppose L satisfies the two conditions given below
(i) L is in NP and
(ii) For every n, there is exactly one string of length n that belongs to L.
Let L^{c} be the complement of L over ∑*. Show that L^{c} is also in NP.
A  Theory Explanation. 
Question 18 
Consider the language L = {a^{n} n≥0} ∪ {a^{n}b^{n} n≥0} and the following statements.
 I. L is deterministic contextfree.
II. L is contextfree but not deterministic contextfree.
III. L is not LL(k) for any k.
Which of the above statements is/are TRUE?
A  II only 
B  III only 
C  I only 
D  I and III only 
We can make DPDA for this.
L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.
Question 19 
Consider the following statements.
 I. If L_{1} ∪ L_{2} is regular, then both L_{1} and L_{2} must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?
A  Both I and II

B  II only 
C  Neither I nor II 
D  I only

Assume L_{1} = {a^{n} b^{n}  n>0} and L_{2} = complement of L_{1}
L_{1} and L_{2} both are DCFL but not regular, but L_{1} U L_{2} = (a+b)* which is regular.
Hence even though L_{1} U L_{2} is regular, L_{1} and L_{2} need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L_{1} = {ab}
L_{2} = {aabb}
L_{3} = {aaabbb}
.
.
.
L_{100} = {a^{100} b^{100}}
.
.
.
If we take infinite union of all above languages i.e,
{L_{1} U L_{2} U ……….L_{100} U ……}
then we will get a new language L = {a^{n} b^{n}  n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.
Question 20 
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?
A  10*(0*10*10*)*

B  ((0 + 1)*1(0 + 1)*1)*10*

C  (0*10*10*)*10* 
D  (0*10*10*)*0*1

The regular expression ((0+1)*1(0+1)*1)*10* generate string “11110” which is not having odd number of 1’s , hence wrong option.
The regular expression (0*10*10*)10* is not a generating string “01”. Hence this is also wrong . It seems none of them is correct.
NOTE: Option 3 is most appropriate option as it generates the max number of strings with odd 1’s.
But option 3 is not generating odd strings. So, still it is not completely correct.
The regular expression (0*10*10*)*0*1 always generates all string ends with “1” and thus does not generate string “01110” hence wrong option.
Question 21 
Which of the following languages are undecidable? Note that
 L_{1} =
L_{2} = {
L_{3} = {
L_{4} = {
A  L_{2} and L_{3} only

B  L_{1} and L_{3} only

C  L_{2}, L_{3} and L_{4} only 
D  L_{1}, L_{3} and L_{4} only 
Only L_{3} is decidable. We can check whether a given TM reach state q in exactly 100 steps or not. Here we have to check only upto 100 steps, so here is not any case of going to infinite loop.
Question 22 
Consider the following language.
L = {x ∈ {a,b}*  number of a’s in x is divisible by 2 but not divisible by 3}
The minimum number of states in a DFA that accepts L is ______.
A  6 
DFA 1: No. of a’s not divisible by 3
Using product automata:
Question 23 
Consider the following languages.
 L_{1} = {wxyx  w,x,y ∈ (0 + 1)^{+}}
L_{2} = {xy  x,y ∈ (a + b)*, x = y, x ≠ y}
Which one of the following is TRUE?
A  L_{1} is contextfree but not regular and L_{2} is contextfree. 
B  Neither L_{1} nor L_{2} is contextfree.

C  L_{1} is regular and L_{2} is contextfree.

D  L_{1} is contextfree but L_{2} is not contextfree. 
So it is equivalent to
(a+b)^{+} a (a+b)^{+} a + (a+b)^{+} b (a+b)^{+} b
L_{2} is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
Question 24 
What is the complement of the language accepted by the NFA shown below?
Assume Σ={a} and ε is the empty string.
A  ∅ 
B  {ε} 
C  a* 
D  {a ,ε} 
Hence the complement of language is: {a* − a^{+}} = {ϵ}
Question 25 
Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a contextfree language, then, is also contextfree?
3) If L is a regular language, then, is also regular?
4) If L is a recursive language, then, is also recursive?
A  1, 2, 3, 4 
B  1, 2 
C  2, 3, 4 
D  3, 4 
Context free languages are not closed under complement operation, so compliment of CFL may or may not be CFL. Hence statement 2 is also undecidable.
Complement of Regular languages is also regular. Since a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its final states with its nonfinal states and viceversa. Hence it is decidable and if L is a regular language, then, L must also be regular.
Recursive languages are closed under complement, so if L is a recursive language then L must also be recursive, hence it is decidable.
Question 26 
Given the language L ={ab,aa,baa}, which of the following strings are in L *?

1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
A  1, 2 and 3 
B  2, 3 and 4 
C  1, 2 and 4 
D  1, 3 and 4 
String 1: abaabaaabaa : ab aa baa ab aa
String 2: aaaabaaaa : aa aa baa aa
String 3: baaaaabaaaab: baa aa ab aa aa b, because of the last “b” the string cannot belong to L*.
String 4: baaaaabaa : baa aa ab aa
Question 27 
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.
The missing arcs in the DFA are
A  
B  
C  
D 
From the state “00” it is clear that if another “0” comes then the string is going to be rejected, so from state “00” the transition with input “0” will lead to state “q”. So option A and B are eliminated.
Now option C has the self loop of “0” on state “10” which will accept any number of zeros (including greater than three zeros), hence the C option is also wrong. We left with only option D which is correct option.
Question 28 
Which two of the following four regular expressions are equivalent? (ε is the empty string).
 (i) (00)*(ε+0)
(ii) (00)*
(iii) 0*
(iv) 0(00)*
A  (i) and (ii) 
B  (ii) and (iii) 
C  (i) and (iii) 
D  (iii) and (iv) 
In these two, we have any no. of 0's as well as null.
Question 29 
Which of the following statements is false?
A  The Halting problem of Turing machines is undecidable. 
B  Determining whether a contextfree grammar is ambiguous is undecidbale. 
C  Given two arbitrary contextfree grammars G1 and G2 it is undecidable whether L(G1) = L(G2). 
D  Given two regular grammars G1 and G2 it is undecidable whether L(G1) = L(G2). 
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1^{st} for CSL and REC.
→ None for RE.
Question 30 
Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?
A  L = {xx has an equal number of a's and b's } is regular 
B  L = {a^{n}b^{n}n≥1} is regular 
C  L = {xx has more a's and b's} is regular 
D  L = {a^{m}b^{n}m ≥ 1, n ≥ 1} is regular 
Here, m and n are independent.
So 'L' Is Regular.
Question 31 
If L_{1} and L_{2} are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?
A  L_{1}, L_{2} 
B  L_{1} ∩ L_{2} 
C  L_{1} ∩ R 
D  L_{1} ∪ L_{2} 
Question 32 
Define for a context free language L ⊆ {0,1}*, init(L) = {u ∣ uv ∈ L for some v in {0,1}∗} (in other words, init(L) is the set of prefixes of L)
Let L = {w ∣ w is nonempty and has an equal number of 0’s and 1’s}
Then init(L) is
A  the set of all binary strings with unequal number of 0’s and 1’s 
B  the set of all binary strings including the null string 
C  the set of all binary strings with exactly one more 0’s than the number of 1’s or one more 1 than the number of 0’s 
D  None of the above 
Question 33 
The grammar whose productions are
→ if id then → if id then else → id := id
is ambiguous because
A  the sentence if a then if b then c:=d 
B  the left most and right most derivations of the sentence if a then if b then c:=d give rise top different parse trees 
C  the sentence if a then if b then c:=d else c:=f has more than two parse trees 
D  the sentence if a then if then c:=d else c:=f has two parse trees 
"if a then if b then c:=d else c:=f".
Parse tree 1:
Parse tree 2:
Question 34 
Consider the given figure of state table for a sequential machine. The number of states in the minimized machine will be
A  4 
B  3 
C  2 
D  1 
Question 35 
Let G be a contextfree grammar where G = ({S, A, B, C},{a,b,d},P,S) with the productions in P given below.
S → ABAC A → aA ∣ ε B → bB ∣ ε C → d
(ε denotes null string). Transform the grammar G to an equivalent contextfree grammar G' that has no ε productions and no unit productions. (A unit production is of the form x → y, and x and y are non terminals.)
A  Theory Explanation. 
Question 36 
Let Q = ({q_{1},q_{2}}, {a,b}, {a,b,Z}, δ, Z, ϕ) be a pushdown automaton accepting by empty stack for the language which is the set of all non empty even palindromes over the set {a,b}. Below is an incomplete specification of the transitions δ. Complete the specification. The top of the stack is assumed to be at the right end of the string representing stack contents.
(1) δ(q_{1},a,Z) = {(q_{1},Za)} (2) δ(q_{1},b,Z) = {(q_{1},Zb)} (3) δ(q_{1},a,a) = {(.....,.....)} (4) δ(q_{1},b,b) = {(.....,.....)} (5) δ(q_{2},a,a) = {(q_{2},ϵ)} (6) δ(q_{2},b,b) = {(q_{2},ϵ)} (7) δ(q_{2},ϵ,Z) = {(q_{2},ϵ)}
A  Theory Explanation. 
Question 37 
Given Σ = {a,b}, which one of the following sets is not countable?
A  Set of all strings over Σ 
B  Set of all languages over Σ 
C  Set of all regular languages over Σ 
D  Set of all languages over Σ accepted by Turing machines 
Question 38 
Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?
A  0*(1+0)* 
B  0*1010* 
C  0*1*01 
D  0(10+1)* 
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
Question 39 
Which one of the following is not decidable?
A  Given a Turing machine M, a stings s and an integer k, M accepts s within k steps 
B  Equivalence of two given Turing machines 
C  Language accepted by a given finite state machine is not empty 
D  Language generated by a context free grammar is non empty 
In (A) the number of steps is restricted to a finite number 'k' and simulating a TM for 'k' steps is trivially decidable because we just go to step k and output the answer.
(B) Equivalence of two TM's is undecidable.
For options (C) and (D) we do have well defined algorithms making them decidable.
Question 40 
Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata?
Note: w^{R} is the string obtained by reversing 'w'.
A  {w⊂w^{R}w ∈ {a,b}*} 
B  {ww^{R}w ∈ {a,b,c}*} 
C  {a^{n}b^{n}c^{n}n ≥ 0} 
D  {ww is a palindrome over {a,b,c}} 
(B) ww^{R}, is realized by NPDA because we can't find deterministically the center of palindrome string.
(C) {a^{n}b^{n}c^{n}  n ≥ 0} is CSL.
(D) {w  w is palindrome over {a,b,c}},
is realized by NPDA because we can't find deterministically the center of palindrome string.
Question 41 
If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is represented by B = ((01)*1*)*, which of the following is true?
A  A ⊂ B 
B  B ⊂ A 
C  A and B are incomparable 
D  A = B 
Question 42 
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
A  The numbers 1, 2, 4, 8, ……………., 2^{n}, ………… written in binary 
B  The numbers 1, 2, 4, ………………., 2^{n}, …………..written in unary 
C  The set of binary string in which the number of zeros is the same as the number of ones 
D  The set {1, 101, 11011, 1110111, ………..} 
10, 100, 1000, 10000 .... = 10*
which is regular and recognized by deterministic finite automata.
Question 43 
Regarding the power of recognition of languages, which of the following statements is false?
A  The nondeterministic finitestate automata are equivalent to deterministic finitestate automata. 
B  Nondeterministic Pushdown automata are equivalent to deterministic Push down automata. 
C  Nondeterministic Turing machines are equivalent to deterministic Pushdown automata. 
D  Both B and C 
C: Power (TM) > NPDA > DPDA.
Question 44 
The string 1101 does not belong to the set represented by
A  110*(0 + 1) 
B  1 ( 0 + 1)* 101 
C  (10)* (01)* (00 + 11)* 
D  Both C and D 
C & D are not generate string 1101.
Question 45 
How many sub strings of different lengths (nonzero) can be found formed from a character string of length n?
A  n 
B  n^{2} 
C  2^{n} 
D 
Possible substrings are = {A, P, B, AP, PB, BA, APB}
Go through the options.
Option D:
n(n+1)/2 = 3(3+1)/2 = 6
Question 46 
Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite 0 state automaton accepting L is
A  2 
B  5 
C  8 
D  3 
Equivalent DFA:
Hence, 5 states.
Question 47 
Which of the following statements is false?
A  Every finite subset of a nonregular set is regular 
B  Every subset of a regular set is regular 
C  Every finite subset of a regular set is regular 
D  The intersection of two regular sets is regular 
Question 48 
Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:
L = {w ∈ {0,1}*  w interpreted as a binary number (ignoring the leading zeros) is divisible by 5}
A  Theory Explanation. 
Question 49 
Let M = ({q_{0}, q_{1}}, {0, 1}, {z_{0}, x}, δ, q_{0}, z_{0}, ∅) be a pushdown automaton where δ is given by
 δ(q_{0}, 1, z_{0}) = {(q_{0}, xz_{0})}
δ(q_{0}, ε, z_{0}) = {(q_{0}, ε)}
δ(q_{0}, 1, X) = {(q_{0}, XX)}
δ(q_{1}, 1, X) = {(q_{1}, ε)}
δ(q_{0}, 0, X) = {(q_{1}, X)}
δ(q_{0}, 0, z_{0}) = {(q_{0}, z_{0})}
(a) What is the language accepted by this PDA by empty stack?
(b) Describe informally the working of the PDA.
A  Theory Explanation. 
Question 50 
(a) Let G_{1} = (N, T, P, S_{1}) be a CFG where,
N = {S_{1}, A, B}, T = {a,b} and
P is given by
S_{1} → aS_{1}b S_{1} → aBb S_{1} → aAb B → Bb A → aA B → b A → a
What is L(G1)?
(b) Use the grammar in part(a) to give a CFG
for L_{2} = {a^{i} b^{j} a^{k} b^{l}  i, j, k, l ≥ 1, i=j or k=l} by adding not more than 5 production rule.
(c) Is L_{2} inherently ambiguous?
A  Theory Explanation. 