automata is accepting all the string starting with 0 including the null string.....compliment should be starting with 1 excluding the null string....C is correct

The Gateway to Computer Science Excellence

+2 votes

+1 vote

Find the smallest length string and then proceed in lexicographic ordering...find out first 3 or 4 string of the language....then compare with the options....if any of the strings is present in the option, it will be discarded

+1 vote

If we try to write the regular expression of the language accepted by above NFA,it looks something like :

$\epsilon + 01^{*} + (01)^{*}$

From the above expression we can say that language L(M) accepts all strings starting with zero or the null string.Or, equivalently in set-builder notation:

$L(M)=\left \{ w:w\epsilon (\left \{ 0,1 \right \}^{*}\wedge {w} \ starts\ with\ zero \vee it's\ a\ null\ string) \right \}$

$\sim L(M)=\left \{ w: w \in \left \{ 0,1 \right \}^{*}\wedge w\ starts\ with\ 1 \right \}$

$So,regex(\sim L(M))=1(0+1)^{*}$

$\epsilon + 01^{*} + (01)^{*}$

From the above expression we can say that language L(M) accepts all strings starting with zero or the null string.Or, equivalently in set-builder notation:

$L(M)=\left \{ w:w\epsilon (\left \{ 0,1 \right \}^{*}\wedge {w} \ starts\ with\ zero \vee it's\ a\ null\ string) \right \}$

$\sim L(M)=\left \{ w: w \in \left \{ 0,1 \right \}^{*}\wedge w\ starts\ with\ 1 \right \}$

$So,regex(\sim L(M))=1(0+1)^{*}$

52,217 questions

59,952 answers

201,133 comments

118,174 users