DFA | Madeeasy TOC

Question

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

Consider the following NFA $N$ as shown below over $\Sigma=\{0\}$.

If $L(N)$ is the language accepted by $N$, then

A $L(N)=L(\bar{N})$

B $\overline{L(N)} \cap L(\bar{N}) \neq \phi$

C $\overline{L(N)} \cup L(\bar{N})=\Sigma^{*}$

D None of these

Comments

$\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.

---

@Abhrajyoti00 so what will be the  $\overline{L(N)}$ and  $L(\overline{N}$) of above NFA?

---

given nfa only accept $\epsilon$ right?

so $L(N)=\epsilon$ so its complement is $0^+$

Answer 1

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