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

+44 votes

0

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

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.

+19 votes

–3 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 .

+2

@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.3k
- Engineering Mathematics 5.1k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.3k
- Admissions 446
- Exam Queries 428
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 8

35,484 questions

42,741 answers

121,445 comments

42,135 users