regex - Finding the complement of a DFA? -

regex - Finding the complement of a DFA? -

i asked show dfa diagram , regex complement of regex (00 + 1)*. in previous problem had prove complement of dfa closed , regular look also, know convert dfa, m complement, m`, need swap initial accepting states , final accepting states.

however, appears initial accepting states regex {00, 1, ^} , final accepting states {00, 1, ^} well. swapping them result in exact same regex , dfa seems contradictory.

am doing wrong or regex supposed not have real complement?

thank you

as says in question:

i know convert dfa, m complement, m`, need swap initial accepting states , final accepting states.

its not complement, doing something reverse of language , regular languages closure under reversal.

reversal of dfa

what reversal language ?

the reversal of language l (denoted lr) language consisting of reversal of strings in l.

given l l(a) fa a, can build automaton lr:

reverse edges (arcs) in transition diagram

the accepting state lr automaton start state a

create new start state new automaton epsilon transitions each of take states

note: reversing arrows , exchanging roles of initial , accepting states of dfa may nfa instead. that's why written fa(not dfa)

complement dfa

finding complement of dfa?

defination: complement of language defined in terms of set difference Σ* (sigma star). l' = Σ* - l.

and complement language (l') of l has strings Σ* (sigma star) except strings in l. Σ* possible strings on alphabet Σ. Σ = set of language symbols

to build dfa d accepts complement of l, convert each accepting state in non-accepting state in d , convert each non-accepting state in take state in d. (warning! not true nfa's)

a dfa of l, d complement

note: build complement dfa, old dfa must finish means there should possible out going border each state(or in other words δ should finish function).

complement: reference example

complement dfa regular look (00+1)*

below dfa named a:

but not dfa not finish dfa. transition function δ partially defined not total domain q×Σ (missing out going border q1 lable 1).

its finish dfa can follows (a):

in above dfa, possible transactions defined (*for every pair of q,Σ *) , δ finish function in case.

reff: larn partial function.

new complement dfa d can constructed changing final states q0 not final states , vice-versa.

so in complement q0 become non-final , q1, q2 final states.

now can write regular look complement language using arden's theorem , dfa given.

here writing regular look complement directly:

(00 + 1)* 0 (^ + 1(1 + 0)*)

where ^ null symbol.

some helpful links: here , through profile can find more helpful answers on fa. also, 2 links on properties of regular language: one, second

regex regular-language automata dfa nfa