Question

Let \(M\) be the 5-state NFA with \(\epsilon\)-transitions shown in the diagram below. 

 Which one of the following regular expressions represents the language accepted by \(M\)?

• A. \((00)^* + 1(11)^*\)
• B. \(0^* + (1 + 0(00)^*)(11)^*\)
• C. \((00)^* + (1 + 0(00)^*)(11)^*\)
• D. \(0^+ + 1(11)^* + 0(11)^*\)

Hint:

For NFAs with \(\epsilon\)-transitions, trace all paths from the start to accept states, combining loops and concatenations to construct the regular expression.

Answer 1

The Correct Option is B

The given NFA \(M\) has five states (\(1, 2, 3, 4, 5\)) and includes \(\epsilon\)-transitions. To determine the language accepted by \(M\), consider the paths and transitions:
1. From state \(1\) to \(2\): The \(\epsilon\)-transition allows state \(2\) to be reached directly without consuming any input.
2. From state \(2\) to \(3\): Input \(0\) can be consumed repeatedly (loop on \(2\)) or proceed to \(3\) with a single \(0\). This corresponds to \((00)^*\).
3. From state \(1\) to \(4\): The \(\epsilon\)-transition allows state \(4\) to be reached directly without consuming any input.
4. From state \(4\) to \(5\): Input \(1\) can be consumed repeatedly (loop on \(5\)) after consuming \(1\). This corresponds to \((11)^*\).
5. Combining paths: The overall language includes all possible combinations:
- \(0^*\), representing sequences of \(0\)'s from state \(2\).
- \((1 + 0(00)^*)(11)^*\), combining sequences starting with \(1\) or sequences starting with \(0\) followed by \((00)^*\), and ending with \((11)^*\). The regular expression representing the language is: \[ 0^* + (1 + 0(00)^*)(11)^*. \] Final Answer: \[ \boxed{\text{(B)}} \]