Automata Gate Previous Year Questions

Which of the following is true?

a) The intersection of two recursively enumerable languages is recursively enumerable.
b) The intersection of two recursive languages is recursive.
c) The intersection of two context free languages is context free.
d) The intersection of two regular languages is regular.

Consider the following language L = {w ∈ {0,1}*| w does not contains three or more consecutive 1's}. The number of states in minimal DFA that accepts L is

Consider the following grammar:
S —> aSb|X
X —>aX|Xb|a|b
What can be said about the language generated by grammar?

a) The regular expression for language generated by the grammar is a*(a + b)b*
b) The language generated by the grammar is non-regular
c) The regular expression for language generated by the grammar is a* b*(a + b)
d) The regular expression for language generated by the grammar is (a + b)*

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

a) (ab*bab*+ ba*aba*)
b) (ab*b)*ab+(ba*a)* ba*
c) (ab*b+ ba*a)* (a*+b*)
d) (ba*a+ ab*b)* (ab*+ba*)

Which of the following is/are undecidable?

a) Given two Turing machines M₁and M₂, decide if L(M₁)=L(M₂).
b) Given a Turing machine M, decide if L(M) is regular.
c) Given a Turing machine M, decide if M accepts all strings.
d) Given a Turing machine M, decide if M takes more than 1073 steps on every string.

Consider the following languages:

a) L1 is not context-free but L2 and L3 are deterministic context-free.
b) Neither L1 nor L2 is context-free.
c) L2, L3, and L2 ∩ L3 all are context-free.
d) Neither L1 nor its complement is context-free.

Which of the following statements is/are TRUE?

a) Every subset of a recursively enumerable language is recursive.
b) If a language L and its complement L are both recursively enumerable, then L must be recursive.
c) The complement of a context-free language must be recursive.
d) If L1 and L2 are regular, then L1∩ L2 must be deterministic context-free.

Suppose that L1 is a regular language and L2 is a context-free language. Which one of the following languages is NOT necessarily context-free?

a) L1∩L2
b) L1⋅L2
c) L1−L2
d) L1∪L2

Consider the following statements.

• S1: The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
• S2: The sequence of procedure returns corresponds to a postorder traversal of the activation tree.

a) S1 is true and S2 is false
b) S1 is false and S2 is true
c) S1 is true and S2 is true
d) S1 is false and S2 is false

Consider the following languages.

a) L1 is regular and L2 is context- free
b) L1 context- free but not regular and L2 is context-free
c) Neither L1 nor L2 is context- free
d) L1 context- free but L2 is not context-free

Which of the following languages are undecidable? Note that ⟨M⟩ indicates encoding of the Turing machine M.

L₁ = { ⟨M⟩ ∣ L(M)=∅ }
L₂ = { ⟨M,w,q⟩ ∣ M on input w reaches state q in exactly 100 steps }
L₃ = { ⟨M⟩ ∣ L(M) is not recursive }
L₄ = { ⟨M⟩ ∣ L(M) contains at least 21 members }

a) L₁, L₃, and L₄ only
b) L₁, and L₃ only
c) L₂, and L₃ only
d) L₂, L₃ and L₄ only

Consider the language L = { aⁿ ∣ n≥0 }∪{ aⁿbⁿ∣ n≥0 } and the following statements.
I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.
Which of the above statements is/are TRUE ?

a) Ⅰ only
b) Ⅱ only
c) Ⅰ and Ⅲ only
d) Ⅲ only

Consider the following statements
I. If L1∪L2 is regular, then both L1 and L2 must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE ?

a) Ⅰ only
b) Ⅱ only
c) Both Ⅰ and Ⅱ
d) Neither Ⅰ nor Ⅱ

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1′s ?

a) ((0+1)*1(0+1)*1)*10*
b) (0*10*10*)*0*1
c) 10*(0*10*10*)*
d) None

Consider the following language.

Consider the following language.
L = { x∈{a,b}* ∣ number of a’s in x divisible by 2 but not divisible by 3 }
The minimum number of states in DFA that accepts L is _________ .

Let Σ be the set of all bijections from {1, ..., 5} to {1, ..., 5}, where id denotes the identity function, i.e. id(j) = j,∀ j. Let ° denote composition on functions. For a string x = x₁ x₂ ... x_n ∈ Σⁿ, n ≥ 0, let π(x) = x₁°x₂° ... °x_n. Consider the language L = {x ∈ Σ* ⏐ π(x) = id}. The minimum number of states in any DFA accepting L is _________ .

Consider the following sets:

a) S₁ and S₂
b) S₃ and S₄
c) S₁ and S₄
d) S₂ and S₃

Which one of the following languages over ∑ = {a, b} is NOT context-free?

a) {ww^R ⏐ w ∈ {a, b}*}
b) {ww^R ⏐ w ∈ {a, b}*}
c) {waⁿw^Rbⁿ ⏐ w ∈ {a, b}*, n≥ 0}
d) {aⁿbiⁱ⏐ i ∈ {n, 3n, 5n}, n≥ 0}

For Σ = {a, b}, let us consider the regular language

a) 3
b) 5
c) 9
d) 24

Consider the following languages:

a) I and IV only
b) I and II only
c) II and III only
d) II and IV only

The minimum possible number of states of a deterministic finite automaton that accepts a regular language L = {w₁aw₂ | w₁, w₂ ∈{a,b}* , |w₁| = 2, w₂>=3} is_______

Identity the language generated by following grammar where S is the start variable.

a) {a^m bⁿ| m>=n, n>0 }
b) {a^m bⁿ| m>=n, n>=0 }
c) {a^m bⁿ | m>n, n>=0 }
d) {a^m bⁿ| m>n, n>0 }

Let L1 and L2 be any context-free language and R be any regular language. Then, which of the following is correct ?

a) I only
b) I and III only
c) II and IV only
d) I, II and IV only

Consider the following grammar:

Consider the language L given by the regular expression (a + b)*b(a +b) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is ______.

Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B* .We say f is computable if there exists a Turning machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denotes the language {x#f(x)|x∈A*}. Which of the following statements is true?

a) f if computable if and only if Lf is recursive.
b) f if computable if and only if Lf is recursive enumerable.
c) if f is computable then Lf is recursive, but not conversely.
d) if f is computable then Lf is recursively enumerable, but not conversely.

Consider the following languages over the alphabet ∑= {a,b,c}.
Let L1 ={aⁿbⁿc^m | m, n >= 0 } and
L2 = {a^mbⁿcⁿ| m, n >= 0}.

Which of the following are context-free languages ?
I. L₁ ∪ L₂
II. L₁ ∩ L₂

a) I only
b) II only
c) I and II
d) Neither I nor II

If G is grammar with productions

a) abab
b) aaab
c) abbaa
d) babba

Consider the following grammar over the alphabet {a,b,c} given below, S and T are non-terminals.

a) Finite
b) Non-finite but regular
c) Context-free but not regular
d) Recursive but not context-free

Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol:

a) {(ab)ⁿ(cb)ⁿ | n >= 1 }
b) {(abⁿcb^m₁cb^m₂...cb^m_n | n, m1, m2, ....., mn >= 1 }
c) {(ab)ⁿ(cb^m)ⁿ | n >= 1 }
d) {(ab)ⁿ(cbⁿ)^m | m, n >= 1 }

Consider the following grammar

a) {R}
b) {w}
c) {w, y}
d) {w, ∉}

The number of states in the minimum sized DFA that accepts the language defined by the regular expression

(0+1)*(0+1)(0+1)*


is __________________

A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example,

int a[10][3];
The grammars use D as the start symbol, and use six terminal symbols int ; id [ ] num.

Grammar G1
D → int L;
L → id [E
E → num]
E → num] [E

Grammar G2
D → int L;
L → id E
E → E[num]
E → [num]

Which of the grammars correctly generate the declaration mentioned above?

a) Both G1 and G2
b) Only G1
c) Only G2
d) Neither G1 nor G2

Which one of the following grammars is free from left recursion?

a) S → AB
A → Aa | b
B → c
b) S → Ab | Bb | c
A → Bd | ε
B → e
c) S → Aa | B
A → Bb | Sc | ε
B → d
d) S → Aa | Bb | c
A → Bd | ε
B → Ae | ε

Consider the following languages.

L₁ = {(M) | M takes at least 2016 steps on some input},
L₂ = {(M) | M takes at least 2016 steps on all inputs} and
L₃ = {(M) | M accepts ε},

where for each Turing machine M, denotes a specific encoding of M. Which one of the following is TRUE?

a) L₁ is recursive and L₂, L₃ are not recursive
b) L₂ is recursive and L₁, L₃ are not recursive
c) L₁, L₂ are recursive and L₃ is not recursive
d) L₁, L₂,L₃ are recursive

Consider the following languages:

L₁= {aⁿb^mc^n+m : m, n >= 1}
L₂= {aⁿbⁿc²ⁿ : n >= 1}

Which one of the following is TRUE?

a) Both L₁ and L₂ are context-free.
b) L₁ is context-free while L₂ is not context-free.
c) L₂ is context-free while L₁ is not context-free.
d) Neither L₁ nor L₂ is context-free.

Consider the following two statements:

I. If all states of an NFA are accepting states then the language accepted by the NFA is Σ* .
II. There exists a regular language A such that for all languages B, A ∩ B is regular.

Which one of the following is CORRECT?

a) Only I is true
b) Only II is true
c) Both I and II are true
d) Both I and II are false

Consider the following types of languages:

L1 Regular,
L2: Context-free,
L3: Recursive,
L4: Recursively enumerable.

Which of the following is/are TRUE?

I. L3' U L4 is recursively enumerable
II. L2 U L3 is recursive
III. L1* U L2 is context-free
IV. L1 U L2' is context-free

a) I only
b) I and III only
c) I and IV only
d) I, II and III only

Language L1 is defined by the grammar:
S1 -> aS1b | ε
Language L2 is defined by the grammar:
S2 -> abS2 | ε
Consider the following statements:

P: L1 is regular
Q: L2 is regular

Which one of the following is TRUE?

a) Both P and Q are true
b) P is true and Q is false
c) P is false and Q is true
d) Both P and Q are false

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y reduces to W, and Z reduces to X (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

a) W can be recursively enumerable and Z is recursive.
b) W an be recursive and Z is recursively enumerable.
c) W is not recursively enumerable and Z is recursive.
d) W is not recursively enumerable and Z is not recursive

Consider the following context-free grammars:

a) {a^mbⁿ |m > 0 or n > 0} and {a^mbⁿ |m > 0 and n > 0}
b) {a^mbⁿ |m > 0 and n > 0} and {a^mbⁿ |m > 0 or n ≥ 0}
c) {a^mbⁿ |m ≥ 0 or n > 0} and {a^mbⁿ |m > 0 and n > 0}
d) {a^mbⁿ |m ≥ 0 and n > 0} and {a ^mbⁿ |m > 0 or n > 0}

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

a) (0+1)*0011(0+1)* + (0+1)*1100(0+1)*
b) (0+1)* (00(0+1) *11+11(0+1)*00)(0+1)*
c) (0+1)*00(0+1) *+ (0+1) *11(0+1) *
d) 00(0+1) *11+11(0+1)*00

Which of the following decision problems are undecidable?

I. Given NFAs N₁ and N₂, is L(N₁)∩L(N₂) = Φ?
II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G₁ and G₂, is L(G₁) = L(G₂)?
IV. Given a TM M, is L(M) = Φ?

a) I and IV only
b) II and III only
c) III and IV only
d) II and IV only

Which of the following languages is generated by the given grammar?

S → aS|bS| ε

a) {aⁿb^m | m,n >= 0}
b) {w∈{a,b}* | w has equal number of a's and b's}
c) {aⁿ | n>=0} U {aⁿbⁿ | n>=0}
d) {a,b}*

For any two languages L₁ and L₂ such that L₁ is context free and L₂ is recursively enumerable but not recursive, which of the following is/are necessarily true?

a) I only
b) III only
c) III and IV only
d) I and IV only

Which one of the following is TRUE?

a) The Language L={ aⁿ bⁿ | n≥ is regular }
b) The Language L={ aⁿ | n is prime }
c) The Language L={ w | w has 3k+1 b's for some k ∈ N with Σ ={a,b}} is regular
d) The Language L={ww | w ∈ Σ with Σ ={0,1}} is regular