edited by
531 views
3 votes
3 votes

Please explain what is difference between $\overline{L(N)}$ and  $L(\overline{N}$) ?

edited by

1 Answer

Best answer
5 votes
5 votes

ANSWER: A,C

$\overline{L(N)}$ means Complement of the language accepted by NFA $N$. This is language complement.

$L(\overline{N})$ means Language accepted by the complement of NFA $N$. This is machine complement.

Given NFA $N$:-

First remove all non-reachable states:-

So $L(N) = \{ϵ\}$ clearly.

Thus $\overline{L(N)}$ which is the Complement of the language accepted by NFA $N = ∑^*-\{ϵ\}$.

 

Now, $\overline{N}$ can be drawn by changing all final to nonfinal states and vice-versa without touching the arrows,

the NFA $(\overline{N})$:-

Thus, $L(\overline{N})$ which is the Language accepted by the complement of NFA $N$ is also $ = \{ ϵ\}$. This is because the starting state itself is the final state. It would have been $\phi$ if there was no final state.

So, we have $L(N) = \{ϵ\}$, $\overline{L(N)}= ∑^*-\{ϵ\}$, $L(\overline{N})=  \{ϵ\}$ 

Option A) $L(N) =  L(\overline{N})=  \{ϵ\}$ TRUE

Option B) $\overline{L(N)}$  intersection $L(\overline{N}) = ∑^*-\{ϵ\}$ intersection  $\{ϵ\} = \phi$. FALSE

Option C) $\overline{L(N)} \cup L(\overline{N}) = ∑^*-\{ϵ\} \cup \{ϵ\} = ∑^*$ . TRUE

 

selected by

Related questions

1 votes
1 votes
1 answer
1
srestha asked Apr 23, 2019
935 views
How many number of $DFA$ states(minimal DFA) required which accepts the language $L=\left \{ a^{n}:n=\text{3 or n>= 2m for all m>= 1} \right \}$ ___________Answer will be...
0 votes
0 votes
1 answer
2
Lakshman Bhaiya asked Dec 27, 2018
546 views
Construct a minimal DFA which accepts set of all strings over {a,b}, such that$1)$Second symbol from $RHS$ should be $‘a’$$2)$Third symbol from $RHS$ should be $‘a�...
1 votes
1 votes
2 answers
3
Shivani gaikawad asked Jun 5, 2018
921 views
The minimum number of state in the DFA for the language $L = \{ w \mid (n_a(w)+2n_b(w))mod \hspace{0.1cm} 3<2 \} $ is
0 votes
0 votes
2 answers
4
Shivani gaikawad asked Jun 5, 2018
442 views
The minimum number of state in the DFA for the language $L = \{ w \mid w \in \{a,b\}^* \text{ w has exactly two a's and at least two b's} \}$ is $9$$10$$16$None