The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes
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?
asked in Theory of Computation by Active (3.6k points) | 364 views

1 Answer

+6 votes
Best answer

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


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.

answered by Boss (38.7k points)
selected by

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"


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. yes

yes...u r correct john

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

36,165 questions
43,622 answers
42,881 users