Computer Sciences > Gate 2024 Set-2 > Thread
Let 𝑀 be the 5-state NFA with 𝜖-transitions shown in the diagram below.
Which one of the following regular expressions represents the language accepted by 𝑀 ?
A
(00)*⁡ + ⁡1(11)*
B
0*+(1+0(00)*)(11)*
C
(00)* + (1+(00)*)(11)*
D
0+ +1(11)* +0(11)*

Correct : c

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.

Similar Questions

Consider a multi-threaded program with two threads T1 and T2. The threads share two semaphores: s1 (initialized to 1) and s2 (initialized to 0). The threads a...
#842 MCQ
Consider the following expression: 𝑥[𝑖]=(𝑝+𝑟)∗−𝑠[𝑖]+𝑢/𝑤. The following sequence shows the list of triples representing the given expression, with entries mi...
#843 MCQ
Consider an array X that contains n positive integers. A subarray of X is defined to be a sequence of array locations with consecutive indices. The C code...
#844 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......