CODEWITHSUNDEEP
dfanfa
Arshia
Arshia

Reputation: 1

NFA to DFA conversion whose language is the complement of L(A)

Can someone please help me with this question?

Describe an algorithm that converts an NFA into a DFA whose language is the complement of L(A). The complement should be taken with respect to the alphabet of A. Given an informal argument for why your construction works. You need not give a formal proof.

Any kind of guidance is appreciated...

Upvotes: 0

Views: 2071

Answers (1)

user684934
user684934

Reputation:

You can convert a FA to its complement by turning its accept states into non-accept states, and turning its non-accept states into accept states. Easy!

You can convert a NFA to a DFA by considering that any NFA state is a power of the states: that is, for each state in the NFA, it is either active or not active. You can map each of these states to a state in a DFA, so you end up with at most 2|Q| states for your DFA which represents your NFA.

Edit: this algorithm and its proof do not actually need the details of A, so long as it is a valid Finite State Automaton.

Upvotes: 0

Related Questions