Question

Consider the NFAM shown below.


Let the language accepted by M be L. let $L_1$ be the language accepted by the NFA$M_1$, obtained by changing the accpeting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

Answer 1

The given machine M is

Now the complementary machine $\overline{M}$ is

In the case of dfa. $L\left(\overline{M}\right)=\overline{L\left(M\right)}$ but in the case

of nfa this is not true. In fact $L\left(\overline{M}\right)$ and L(M) have no connection

$\therefore$ To find $L_1=L\left(\overline{M}\right)$ we have to look at $\overline{M}$ and directly find its language

$L_1=L\left(\overline{M}\right)=ϵ+(0+1)(0+1{)}^{\ast }+....$

= $(0+1{)}^{\ast }+=(0+1{)}^{\ast }$