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

NFA to regular expression GATE Computer Science 2024 NFA language representation computer science gate regular expressions NFA NFA diagram analysis convert NFA regex NFA transition table

Unique Visitor Count

Total Unique Visitors

Loading......