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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+32 votes

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?

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

0

Assume $Σ={a}$ and $ϵ$ is the empty string.

$L=\left\{a^{+}\right\}$

$(1)$ What is the complement of the language accepted by the $NFA?$

$\overline{L}=\left\{ϵ\right\}$

$(2)$ What is the language which accepts complement of $NFA?$

$L_{1}=\left\{ϵ,(a+ϵ)^{+}\right\}$

Please correct me if i'm wrong$?$

+50 votes

+2

How will aa be produced here ? after one a it goes to final state . What hapens on reading the 2nd 'a' ?

+15

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

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.

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.

+2

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.

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

+28 votes

–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 a^{* }is the answer

+4

@Monika its complement of the language i.e.**L ^{c} =∑*-L.**

and you are talking about complement of machine .

+4

@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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,817 users