Automata GATE previous year questions with answer

Explanation:
Let us trace the languages accepted by the upper and lower paths of the $\epsilon$-NFA from the initial state 1.
1. Upper Path (States 1 → 2 → 3): • From state 1, we can reach state 2 on an empty transition ($\epsilon$). State 2 is an accepting state.
• Moving back and forth between state 2 and state 3 requires reading exactly two 0s (2 → 3 reads 0, 3 → 2 reads 0).
• Therefore, the language accepted purely within the upper component loop is any even number of 0s: (00)*.

2. Lower Path and Cross-Over Transitions to State 5: State 5 is the other final accepting state. Let's see all the distinct structural paths that can end at state 5:

• Path A (Directly through the bottom loop):
    • Go from 1 → 4 via $\epsilon$.
    • Go from 4 → 5 by reading a single 1.
    • Once at state 5, we can loop back and forth to state 4 by reading pairs of 1s (5 → 4 → 5 is 11). This gives (11)*.
    • Combining these parts gives the expression: 1(11)*.

• Path B (Cross-over from the top component):
    • We can spend any number of even 0s in the upper loop, ending up at state 3. This is represented by (00)*0.
    • From state 3, we can transition to state 5 via $\epsilon$.
    • Once at state 5, we can loop an arbitrary number of times using pairs of 1s, which adds (11)*.
    • Combining these gives: (00)*0(11)*, which simplifies structurally to matching an odd number of 0s followed by an even number of 1s.

### 3. Combine and Simplify the Sub-expressions: Let's look at the collective path heading into the (11)* loop at state 5:
• Via Path A: we provide a 1.
• Via Path B: we provide an odd sequence of 0s, which is 0(00)* or equivalent combinations.

Looking at option (c): (00)* + (1 + (00)*)(11)*. Let's expand the right side:
    1(11)* + (00)*(11)*

Since (00)* includes the $\epsilon$ string (zero 0s), (00)*(11)* covers (11)* directly, as well as any even number of 0s followed by an even number of 1s. This perfectly matches the reachable state-space criteria of the automation design.

Conclusion: Option (c) is the correct regular expression mapping for machine M.

a) is correct

The class of recursively enumerable (RE) languages is closed under intersection.
If L1 and L2 are RE languages, then L1 ∩ L2 is also RE.
This can be done by constructing a Turing machine that runs the machines for both L1 and L2 in parallel and accepts if both accept.
For example:
Let L1 = { w | w contains at least one 'a' } and L2 = { w | w contains at least one 'b' }.
Their intersection is L1 ∩ L2 = { w | w contains both 'a' and 'b' }, which is RE.

b) is incorrect

The class of recursive languages is not always closed under intersection.
If L1 and L2 are recursive, their intersection L1 ∩ L2 might not necessarily be recursive because deciding membership in L1 ∩ L2 could require undecidable steps.
For example:
Let L1 = { w | w halts on input 0 } and L2 = { w | w halts on input 1 }.
Their intersection is L1 ∩ L2 = { w | w halts on both input 0 and input 1 }, which is not recursive because the halting problem is undecidable.

c) is incorrect

The class of context-free languages (CFLs) is not closed under intersection.
There exist CFLs L1 and L2 such that their intersection L1 ∩ L2 is not a CFL.
For example:
Let L1 = { an bn cm | n, m ≥ 0 } and L2 = { am bn cn | n, m ≥ 0 }.
Their intersection is L1 ∩ L2 = { an bn cn | n ≥ 0 }, which is not a CFL.

d) is correct

The class of regular languages is closed under intersection.
If L1 and L2 are regular, then L1 ∩ L2 is also regular.
This can be achieved using the product construction of finite automata.
For example:
Let L1 = { w | w starts with 'a' } and L2 = { w | w ends with 'b' }.
Their intersection is L1 ∩ L2 = { w | w starts with 'a' and ends with 'b' }, which is regular.

So, a, c, d is correct option