GATE CS 2003 Q55 — Regular Expressions and Finite Automata

In the given NFA $M$:

• The start state $q_0$ has self-loops for both input symbols $0$ and $1$.
• The only accepting state is $q_2$, while $q_0$ and $q_1$ are non-accepting states.

To construct the NFA $M_1$, we swap the accepting and non-accepting states of $M$:

• The states $q_0$ and $q_1$ become accepting states in $M_1$.
• The state $q_2$ becomes a non-accepting state.

Since the start state $q_0$ is now an accepting state in $M_1$, and it has self-loops on both $0$ and $1$, any string $w \in \{0,1\}^*$ can be processed by remaining in $q_0$. Because $q_0$ is an accepting state, every string is accepted by $M_1$.

Thus, the language accepted by $M_1$ is: