Consider the NFA M shown below. Let the language accepted by M be L. Let L₁ be…
2003
Consider the NFA M shown below. Let the language accepted by M be L. Let L₁ be the language accepted by the NFA M₁, obtained by changing the accepting state and by changing the non-accepting states of M to accepting states. Which of the following statements is true?
- A.
L₁ = {0,1}* − L
- B.
L₁ = {0,1}*
- C.
L₁ ⊂ L
- D.
L₁ = L
Attempted by 41 students.
Show answer & explanation
Correct answer: B
First, observe the original NFA M. The start state (leftmost circle) has a self-loop labeled "1, 0", meaning it can read any input symbol and remain in the same state.
Next, consider the modified NFA M₁. The problem specifies that accepting and non-accepting states are swapped, so the original start state becomes an accepting state in M₁.
Since the start state is now accepting and has a self-loop on all input symbols, any string can be processed by staying in this state. Thus, every string over {0, 1} is accepted.
Therefore, the language L₁ accepted by M₁ is {0, 1}*.
A video solution is available for this question — log in and enroll to watch it.