440 views
To complement the language , we complement the machine by altering final/non-final states.

My question is , should that machine necessarily be a DFA? Can't we apply the same concept to NFA?

First you should know the difference between these two term.

(1)Complement of Language

(2)Complement of Machine

Complement of Language

$L^{c}=\sum ^{*}-L$

Suppose you have language $L=a^{+}$ over $\sum =\left ( a \right )$.

$L^{c}=a^{*}-a^{+}$

So $L^{c}=\epsilon$

Complement of Machine

Let M be any finite automata then the complement of the machine can be obtained by swapping its accepting states with its non-accepting states and vice versa.Let us take an example,

This DFA accepts the language  $L=\left \{ a,aa,aaa,aaaa,............ \right \}$

over the alphabet $\sum =\left ( a,b \right )$.

Now we will swap its accepting states with its non-accepting states and vice versa and will get the following −

This DFA accepts the language $L=\left \{ \epsilon ,b,ab,bb,....... \right \}$.

In case of DFA complementation the language is also complemented i.e.

$L(M^{c})=\left ( L\left ( M \right ) \right )^{c}$.

But this is not hold true in case of NFA , the language may or may not  complemented.

That,s it.

selected
+6

JOHN though manoj explained well .....but  it may help you...i m providing the example of NFA whose complement...doesnot complements the language,..
consider  a language L= " strings starting with 0" over ∑={0,1} where q1 is initial stage and q2 is final stage..
whoser nfa is

after complement it becomes

here q1 is final ..the language accepted by this is only null string...

but....actually..if we complement the language L= " strings starting with 0" over ∑={0,1}  we should get...the  language which accepts both...the "null string and  the language starting with 1"

+1

Thank You Sir,

After this discussion I can conclude that ," complement of an NFA may or may not give the complement of the Language , But  Complement of the DFA certainly give the Complement of the Language".

If any corrections required in the Statement above do Comment.

0
yes...u r correct john

1
2
3
4
5
6