The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes

Ans. C

asked in Theory of Computation by Loyal (6.6k points) | 110 views
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

4 Answers

+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
answered by (349 points)
+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)^{*}$
answered by Junior (849 points)
+1 vote

option c is right.

answered by Boss (33.9k points)
0 votes
The NFA represents the null string, starts with 0 and followed by anything so compliments is nothing but 1 followed by anything.
answered by (107 points)
B not be answer because there is union

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,576 questions
54,182 answers
71,144 users