Automata GATE previous year questions with answer

Given:
Language L₁ grammar: S₁ → aS₁b | ε
Language L₂ grammar: S₂ → abS₂ | ε
Statements:
P: L₁ is regular
Q: L₂ is regular
To find:
Which statement is TRUE among the given options.
Solution:
First, let me look at the language L₁.
Starting from S₁, applying S₁ → aS₁b repeatedly gives strings like ε, ab, aabb, aaabbb, and so on.
So, L₁ = {aⁿbⁿ | n ≥ 0}.
A finite automaton cannot keep track of an arbitrary number of a's to match with b's because it has finite memory.
By the pumping lemma, this is a standard non-regular language.
So L₁ is not regular, which means statement P is false.
Now let me analyze language L₂.
Starting from S₂, the production S₂ → abS₂ generates repeated copies of "ab".
When it terminates with ε, the strings generated are ε, ab, abab, ababab, and so on.
So, L₂ = {(ab)ⁿ | n ≥ 0}.
I can write the regular expression for this directly as (ab)*.
Since it has a valid regular expression and can easily be recognized by a simple DFA with two states, L₂ is regular.
This means statement Q is true.
Hence, P is false and Q is true.
Answer: (C) P is false and Q is true

Given:
Language X is recursive (REC).
Language Y is recursively enumerable but not recursive (RE but not REC).
Y ≤_m W and Z ≤_m X.
To find:
The correct statement among the given options.
Solution:
First, let me recall the standard properties of many-one reduction (A ≤_m B):
1. If B is recursive, then A must also be recursive.
2. If B is recursively enumerable, then A must also be recursively enumerable.
Taking the contrapositive:
3. If A is not recursive, then B cannot be recursive.
4. If A is not RE, then B cannot be RE.
Now let's analyze Z ≤_m X:
We are given that X is recursive.
Since Z reduces to a recursive language X, Z must be recursive.
So, Z is definitely recursive.
Now let's analyze Y ≤_m W:
We know Y is not recursive.
By property 3, W cannot be recursive (if W were recursive, Y would be recursive, which is a contradiction).
Can W be recursively enumerable? Yes, because if we pick W = Y, then Y ≤_m Y holds, and W is RE.
W can also be not RE (for example, reducing to a non-RE language).
Therefore, W can be recursively enumerable.
Combining both results, W can be recursively enumerable and Z is recursive.
Answer:
(A) W can be recursively enumerable and Z is recursive.

Given:
Context-free grammars:
G1: S → aS | B, B → b | bB
G2: S → aA | bB, A → aA | B | ε, B → bB | ε
To find:
The languages generated by G1 and G2.
Solution:
First, let me analyze grammar G1.
Looking at the non-terminal B:
B → b | bB
This means B produces at least one 'b', so B generates b⁺, or bⁿ where n ≥ 1 (that is, n > 0).
Now looking at the start symbol S:
S → aS | B
S can produce zero or more 'a's before switching to B.
So S generates a*B, which gives a^mbⁿ where m ≥ 0 and n > 0.
Therefore, L(G1) = {a^mbⁿ | m ≥ 0 and n > 0}.
Now let me analyze grammar G2.
First, look at B:
B → bB | ε, which means B generates b* (zero or more 'b's).
Next, look at A:
A → aA | B | ε, which generates a*B = a*b*.
Now, look at the productions for start symbol S:
S → aA | bB
Case 1: S → aA
Since A generates a*b*, aA produces strings with at least one 'a' followed by any number of 'b's (including zero 'b's).
So this case gives a^mbⁿ where m ≥ 1 and n ≥ 0.
Case 2: S → bB
Since B generates b*, bB produces strings with zero 'a's and at least one 'b'.
So this case gives a^mbⁿ where m = 0 and n ≥ 1.
Combining both cases from S, the grammar generates all strings of the form a^mbⁿ except the empty string (m = 0, n = 0).
So at least one of m or n must be strictly positive.
This gives the condition: m > 0 or n > 0.
Therefore, L(G2) = {a^mbⁿ | m > 0 or n > 0}.
Comparing with the given choices, this matches Option D.
Answer:
(D)

Given:
Language: Set of all binary strings containing both two consecutive 0s and two consecutive 1s.
Alphabet: Σ = {0, 1}.
To find:
The correct regular expression for this language.
Solution:
The condition states that every string in the language must contain the substring "00" AND the substring "11".
Since "00" and "11" share no common characters, they cannot overlap at all.
This means in any valid string, either "00" comes before "11", or "11" comes before "00".
Let me write the regular expression for the first case, where "00" appears before "11":
(0+1)*00(0+1)*11(0+1)*
Now for the second case, where "11" appears before "00":
(0+1)*11(0+1)*00(0+1)*
Combining both cases using union (+), I get:
(0+1)*00(0+1)*11(0+1)* + (0+1)*11(0+1)*00(0+1)*
Now I can factor out (0+1)* from the left and right sides:
(0+1)*(00(0+1)*11 + 11(0+1)*00)(0+1)*
Let me check the other options just to be completely sure.
Option A requires "00" and "11" to be immediately adjacent to each other, so it misses strings like "001011".
Option C uses union between the two conditions, which represents strings with "00" OR "11", not AND.
Option D forces the string to start with "00" or "11" and end with "11" or "00", so it misses strings like "100110".
So only option B correctly captures the required language.
Answer:
(B) (0+1)* (00(0+1) *11+11(0+1)*00)(0+1)*

Given:
Four decision problems:
I. For NFAs N₁ and N₂, is L(N₁) ∩ L(N₂) = Φ?
II. For a CFG G and a string x, does x ∈ L(G)?
III. For CFGs G₁ and G₂, is L(G₁) = L(G₂)?
IV. For a TM M, is L(M) = Φ?
To find:
Which of these decision problems are undecidable.
Solution:
Let me check each problem one by one.
First, looking at problem I:
Regular languages are closed under intersection, so L(N₁) ∩ L(N₂) is also regular.
Emptiness for regular languages is decidable by checking reachability of a final state from the start state.
So, problem I is decidable.
Now, looking at problem II:
This is the membership problem for Context-Free Grammars.
We can use the CYK algorithm to decide if x ∈ L(G) in polynomial time.
So, problem II is decidable.
Next, looking at problem III:
This is the equivalence problem for Context-Free Grammars.
Equivalence of two CFGs is a standard undecidable problem (it can be reduced from the Post Correspondence Problem).
So, problem III is undecidable.
Finally, looking at problem IV:
This is the emptiness problem for Turing Machines.
Emptiness is a non-trivial property of the language of a TM, so by Rice's theorem, it is undecidable.
So, problem IV is undecidable.
Therefore, the undecidable problems are III and IV.
Answer: (C) III and IV only

Given:
Grammar production rules: S → aS | bS | ε.
To find:
The language generated by the given grammar.
Solution:
Let me look at the productions given for the start symbol S.
S can expand to aS, meaning it can generate an 'a' and continue generating.
S can also expand to bS, meaning it can generate a 'b' and continue generating.
And finally, S can expand to ε, which terminates the derivation.
Let me test a few strings to see what can be formed.
If I just choose S → ε, I get the empty string ε.
If I choose S → aS → aε = a, I get string "a".
If I choose S → bS → bε = b, I get string "b".
If I want an arbitrary string like "baab":
S → bS → baS → baaS → baabS → baabε = baab.
So clearly, at any position, I can choose either 'a' or 'b' freely without any restriction on order or count.
Once I am done, I can just replace S with ε to stop.
This means the grammar can generate any sequence of 'a's and 'b's of any length, including length 0.
Therefore, the regular expression for this language is (a + b)*.
In set notation, this is equal to {a, b}*.
Looking at the options, this directly matches option D.
Answer: (D) {a,b}*

L1 is context-free and L2 is recursively enumerable but not recursive.
Statement I — True: Every CFL is recursive, and recursive languages are closed under complement. Since L1 is CFL → L1 is recursive → L1'' is recursive.
Statement II — False: L2 is RE but not recursive. If L2'' were recursive, it would also be RE, and having both L2 and L2'' be RE would imply L2 is recursive — a contradiction. So L2'' is not recursive.
Statement III — False: CFLs are not closed under complementation. The complement of a CFL need not be context-free. For example, the complement of {aⁿbⁿcⁿ : n≥1} is CFL but not all CFL complements are CFLs. So L1'' is not necessarily context-free.
Statement IV — True: From I, L1'' is recursive, so L1'' is also RE. L2 is RE. RE languages are closed under union. Therefore L1'' ∪ L2 is RE.
Correct answer: D — I and IV only. Your page''s answer display is a bug showing "CFG" instead of D ✓

The question asks which of the given languages is regular.
Analyze the Options:
A) L = { aⁿbⁿ | n ≥ 0 }: This language requires the number of a's to be equal to the number of b's. A finite automaton cannot keep track of equal numbers of a's and b's. Therefore, it is not regular.
Example: ab, aabb, aaabbb are in the language, but aab and abb are not.
B) L = { aⁿ | n is prime }: The language contains strings whose length is a prime number. A finite automaton cannot determine whether an arbitrarily large number is prime. Therefore, it is not regular.
Example: a², a³, a⁵ are in the language, but a⁴ and a⁶ are not.
C) L = { w | w has 3k+1 b's for some k ∈ N, with Σ = {a,b} }: The number of b's must be of the form 3k+1. A finite automaton can keep track of the number of b's modulo 3. Therefore, this language is regular.
Example: If k = 0, the string can have 1 b, such as "b" or "ab". If k = 1, it must have 4 b's, such as "bbbb" or "abbbba". If k = 2, it must have 7 b's. Hence, the language accepts strings with 1, 4, 7, 10, ... b's.
D) L = { ww | w ∈ Σ, with Σ = {0,1} }: This language contains strings formed by repeating the same string twice. A finite automaton cannot generally remember the first half and compare it with the second half. Therefore, it is not regular.
Example: 00, 0101, and 1010 are in the language, while 0010 and 0110 are not.
Correct Answer: C) The Language L = { w | w has 3k+1 b's for some k ∈ N with Σ = {a,b} } is regular.