Weak DBW 

Example 1: We know that L_w=lim(L_*). But this example shows that we can have two MINIMAL DFAs which produce the same set of infinite words. I.e. the two DBWs represent the same infinite language but with different number of internal states.  

Example 2: For weak DBWs we always have the same minimal number of internal states. 

>
 

Example Collection 

> ## Generating wDBW
conti:=true:
while conti do
dfa1:=reachableDFA(randomDFA(rand(20)()+6,{0,1},rand(4)()+2)):
F:=op(5,dfa1):
limSet:=limNBW(DFA2DBW(dfa1));
conti:=false:
for scc in limSet do
 if not((scc intersect F)=scc or (scc intersect F)={}) or
    nops(limSet)<=2 or nops(F intersect map(op,limSet))<=3 then
  conti:=true:
  break:
 fi:
od:
od:
dfa1:=subsop(5=(F intersect map(op,limSet)),dfa1);
 

`:=`(dfa1, DFA({q0, q1, q3, q7, q8}, {0, 1}, TABLE([(q3, 0) = q3, (q7, 1) = q1, (q8, 0) = q8, (q0, 0) = q7, (q7, 0) = q7, (q1, 1) = q8, (q0, 1) = q0, (q3, 1) = q1, (q1, 0) = q3, (q8, 1) = q8]), q0, {q...
`:=`(dfa1, DFA({q0, q1, q3, q7, q8}, {0, 1}, TABLE([(q3, 0) = q3, (q7, 1) = q1, (q8, 0) = q8, (q0, 0) = q7, (q7, 0) = q7, (q1, 1) = q8, (q0, 1) = q0, (q3, 1) = q1, (q1, 0) = q3, (q8, 1) = q8]), q0, {q...		 (18.6.1)
 

> limNBW(DFA2DBW(dfa1));
dfa2:=(minimalDFA(dfa1)):
limNBW(DFA2DBW(dfa2));
transitionGraph(dfa1);
transitionGraph(dfa2);
 

{{q4}, {q10}, {q5}, {q1}, {q16, q12}}
 

{{{q5, q4, q10}}, {{q1}}, {{q16}, {q12}}}
 

Plot_2d
 

Plot_2d
 

> DFA2RE(dfa1,result=string);
DFA2RE(dfa2,result=string);
 

( 1 . 0 * . ( 1 + ( 1 . ( 1 + 0 ) ) . ( 0 . ( 1 + 0 ) ) * . ( lambda + 0 ) ) ) (18.6.2)
 

( 1 . 0 * . 1 + ( 1 . 0 * . 1 . ( 0 + 1 ) ) . ( 0 . ( 0 + 1 ) ) * . ( lambda + 0 ) ) (18.6.2)
 

>
 

> dfa2:=(minimalDFA(dfa1)):
while (nops(op(1,dfa1))= nops(op(1,dfa2))) or (nops(limNBW(DFA2DBW(dfa1))) = nops(limNBW(DFA2DBW(dfa2)))) do
 dfa1:=reachableDFA(randomDFA(6,{0,1},3)):dfa2:=(minimalDFA(dfa1)):
od:
limNBW(DFA2DBW(dfa1));
limNBW(DFA2DBW(dfa2));
transitionGraph(dfa1);
transitionGraph(dfa2);