The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+31 votes
3.4k views

What is the complement of the language accepted by the NFA shown below?
Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string.

  1. $\phi$
  2. $\{\epsilon\}$
  3. $a^*$
  4. $\{a , \epsilon\}$



  

asked in Theory of Computation by Boss (18.3k points)
edited by | 3.4k views
0
What will be the NFA for the complement of the lang?

All state transition arrows will be reversed and non-final states will be final and vice-versa. Is it correct?
+1
arrows will not be reversed.....

6 Answers

+47 votes
Best answer
The language being accepted is $a^+$. So, complement of the language is $\{\epsilon\}$.
answered by Veteran (370k points)
selected by
+1
How will aa be produced here ?  after one a it goes to final state . What hapens on reading the 2nd 'a'  ?
+11
@gokou from final state using epsilon we can again come back to start state..and the process repeats!!
0
Is this true?: If L = $\phi$ then L* = $\{\epsilon\}$
0
@habed yes true
0
Sir, I have the same query. If in complementation, arrows are not reversed, then there are always epsilon paths from the non-final state(middle state) to the final states. So language accepted should be a*.

But again, your solution also seems very right.  I fail to understand what's going on.

It would be really helpful if you can clarify this doubt.
+1

In Complementation, arrows are not reversed but final states are exchanged so that change the whole language .

Example: make DFA of a* now if you complete the DFA then there is no Final state i.e. accept Nothing.

Take another language a*b* make DFA of it and complement it , Then you get the idea.

0
Plss someone clarify why answer is not a*. According to me suppose we give input string 'aaa'. Then using epsilon transitions we can reach the final state. overall it can generate a*.

Plss help.
+1
@mbisht complement rule is not applicable on NFA it is applicable on dfa so first convert it into dfa then come to point .....u should read prashant sir comment
0
Thankss...I got it.
0

 from final state using epsilon we can again come back to start state..and the process repeats!!

using the same logic, even in complement of NFA this should work. 

Plz help 

0
@Arjun sir how dfa will look like for this nfa ? Can we just remove epsilon transitions and can consider it as dfa? Or shall we use nfa to dfa conversion method?
+25 votes
NFA accepts the language L=a+ and ∑={a}

the complement of L=∑*- a+=a*-a+={∊}

so answer is B
answered by Active (2.7k points)
0
Complement does not work with NFA always. I don't think this approach is correct even though it works for this example.
+3 votes
the language is a+ .....  compliment is {$\varepsilon$}
answered by (99 points)
edited by
+2 votes

Ans.

answered by Junior (807 points)
–2 votes

answer is c.  for complement of the language: changes to be done in DFA is to make final states to non final states and make non final to final states. then check. so ais the answer

answered by (33 points)
edited by
+4

@Monika its complement of the language i.e.Lc =∑*-L.

and you are talking about complement of machine .

+3
@Monika the machine given is NFA and not DFA. So, you can't complement the machine and get the language. Correct answer is B
0
@Nipun No.Here qus is complement of the language accepted by the NFA not complement of machine accepted by NFA.
0
No. What he meant was - in order to change final states to non final state. You need to convert that NFA to DFA. Only then, the machine would accept the complement of the language.
+1

No Actually i mean you can complement NFA but  in case of NFA , the language may or may not  complemented.

You can check this :https://gateoverflow.in/53393/theory-of-computation

–4 votes
option B
answered by Loyal (6.9k points)
0

what steps do we have to follow while converting M to M bar.



Answer:

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

44,462 questions
49,918 answers
165,461 comments
65,898 users