Deterministic Finite Accepters
| > | InternalStates:={q0,q1,q2}:
Alphabet:={`0`,`1`}: delta:=table(): delta[(q0,`0`)]:=q0: delta[(q0,`1`)]:=q1: delta[(q1,`0`)]:=q0: delta[(q1,`1`)]:=q2: delta[(q2,`0`)]:=q2: delta[(q2,`1`)]:=q1: InitialState:=q0: FinalStates:={q1}: dfa:=mkDFA(InternalStates,Alphabet,op(delta),InitialState,FinalStates); |
![`:=`(dfa, DFA({q0, q1, q2}, {`0`, `1`}, TABLE([(q0, `1`) = q1, (q2, `0`) = q2, (q2, `1`) = q1, (q0, `0`) = q0, (q1, `1`) = q2, (q1, `0`) = q0]), q0, {q1}))](images/FOLA-demo_48.gif){kind=small} ![`:=`(dfa, DFA({q0, q1, q2}, {`0`, `1`}, TABLE([(q0, `1`) = q1, (q2, `0`) = q2, (q2, `1`) = q1, (q0, `0`) = q0, (q1, `1`) = q2, (q1, `0`) = q0]), q0, {q1}))](images/FOLA-demo_49.gif){kind=small} |
(5.1) |
| > | transitionGraph(dfa); |
 |
Random DFA:
String Verification
Find Sentences
Removing unreachable states
Partition
Minimalization
| > | while true do
dfa:=reachableDFA(randomDFA(6,[0,1],3,initialState='q0',internalStateStartingSymbol='q')): dfa2:=minimalDFA(dfa): if nops(op(1,dfa)) > nops(op(1,dfa2))+2 then break; fi: od: |
| > | dfa; |
   |
(5.6.1) |
| > | dfa2; |
   |
(5.6.2) |
| > |
Examples:
| > | dfa:=mkNFA({q0, q1, q2, q3, q4, q5,q6},{0, 1},table([(q5, 0) = q1, (q4, 0) = q3, (q3, 1) = q5, (q4, 1) = q3, (q0, 1) = q2, (q5, 1) = q3, (q3, 0) = q5, (q0, 0) = q2, (q1, 1) = q4, (q2, 1) = q5, (q1, 0) = q5, (q2, 0) = q0]),q0,{q1, q2, q3}):
transitionGraph(dfa); |
 |
| > | transitionGraph(minimalDFA(NFA2DFA(dfa))); |
 |
| > | dfa:=DFA({q0, q1, q2, q3, q4, q5},{0, 1},table([(q5, 0) = q3, (q4, 0) = q5, (q3, 1) = q1, (q4, 1) = q4, (q0, 1) = q3, (q5, 1) = q4, (q3, 0) = q2, (q0, 0) = q5, (q1, 1) = q4, (q2, 1) = q4, (q1, 0) = q5, (q2, 0) = q5]),q0,{q0, q1, q4}):
transitionGraph(dfa); |
 |
| > | transitionGraph(minimalDFA(dfa)); |
 |
| > | dfa:=DFA({q0, q1, q2, q3, q5},{0, 1},table([(q5, 0) = q5, (q3, 1) = q2, (q0, 1) = q3, (q5, 1) = q1, (q3, 0) = q5, (q0, 0) = q5, (q1, 1) = q5, (q2, 1) = q2, (q1, 0) = q1, (q2, 0) = q5]),q0,{q1, q5}):
transitionGraph(dfa); |
 |
| > | transitionGraph(minimalDFA(dfa)); |
 |
| > | dfa:=mkDFA({q0, q1, q2, q3, q4, q5,q6},{0, 1},table([(q5, 0) = q3, (q4, 0) = q3, (q3, 1) = q3, (q4, 1) = q0, (q0, 1) = q2, (q5, 1) = q1, (q3, 0) = q5, (q0, 0) = q5, (q1, 1) = q2, (q2, 1) = q2, (q1, 0) = q4, (q2, 0) = q5, (q5,0) = q6, (q6,0) = q6, (q6,1) = q6]),q0,{q0, q1, q2,q6}):
transitionGraph(dfa); |
 |
| > | partitionDFA(dfa); |
 |
(5.6.1.1) |
| > | transitionGraph(minimalDFA(dfa)); |
 |
| > | dfa:=mkDFA({q0, q1, q2, q3, q4, q5},{0, 1},table([(q5, 0) = q5, (q4, 0) = q5, (q3, 1) = q2, (q4, 1) = q1, (q0, 1) = q2, (q5, 1) = q2, (q3, 0) = q2, (q0, 0) = q4, (q2, 1) = q3, (q1, 1) = q2, (q1, 0) = q2, (q2, 0) = q5]),q0,{q0, q1, q3, q5}):
transitionGraph(dfa); |
 |
| > | transitionGraph(minimalDFA(dfa)); |
 |
| > | dfa:=randomDFA(6,[0,1],2,initialState='q0',internalStateStartingSymbol='q');
|
   |
(5.6.3) |
| > | op(1,dfa); |
 |
(5.6.4) |
| > | dfa1:=randomDFA(6,[0,1],2,initialState='q0',internalStateStartingSymbol='q');
dfa2:=minimalDFA(dfa); |
   |
(5.6.5) |
   |
(5.6.5) |
    |
(5.6.5) |
Equivalence of the DFAs
| > | isEmptyNFA(complementNFA(unionNFA(complementNFA(dfa),dfa2)));
isEmptyNFA(complementNFA(unionNFA(complementNFA(dfa2),dfa))); |
 |
(5.6.6) |
 |
(5.6.6) |
| > | isEmptyNFA(intersectNFA(dfa,complementNFA(dfa2)));
isEmptyNFA(intersectNFA(dfa2,complementNFA(dfa))); |
 |
(5.6.7) |
 |
(5.6.7) |
| > | isEquivalentNFA(dfa,dfa2); |
 |
(5.6.8) |
| > | dfa := DFA({q0, q1, q2, q3, q4},{0, 1},table([(q3, 1) = q0, (q2, 0) = q0, (q1, 1) = q3, (q4, 0) = q4, (q2, 1) = q1, (q1, 0) = q3, (q0, 0) = q2, (q0, 1) = q1, (q4, 1) = q0, (q3, 0) = q3]),q0,{q0, q1, q2}): |
| > | dfa := DFA({q0, q1, q2, q3, q4, q5},{0, 1},table([(q3, 1) = q4, (q2, 0) = q5, (q1, 1) = q3, (q4, 0) = q5, (q5, 1) = q4, (q2, 1) = q4, (q1, 0) = q0, (q5, 0) = q2, (q0, 0) = q4, (q0, 1) = q0, (q4, 1) = q2, (q3, 0) = q5]),q0,{q2, q5}): |
| > | dfa := DFA({q0, q1, q2, q3, q4, q5},{0, 1},table([(q3, 1) = q4, (q2, 0) = q1, (q1, 1) = q4, (q4, 0) = q3, (q5, 1) = q0, (q2, 1) = q2, (q1, 0) = q3, (q5, 0) = q4, (q0, 0) = q5, (q0, 1) = q4, (q4, 1) = q2, (q3, 0) = q3]),q0,{q1, q3}): |
| > | dfa := DFA({q0, q1, q2, q3, q4},{0, 1},table([(q3, 1) = q4, (q2, 0) = q3, (q1, 1) = q2, (q4, 0) = q1, (q2, 1) = q3, (q1, 0) = q4, (q0, 0) = q3, (q0, 1) = q4, (q4, 1) = q2, (q3, 0) = q0]),q0,{q1, q4}): |
| > |
| > | transitionGraph(dfa); |
 |
| > | dfa2:=minimalDFA(dfa);
transitionGraph(dfa2); |
   |
 |
| > | dfa:=mkDFA([q0, q1, q2, q3, q4, q5], [a1, a2, a3], table([(q4, a1) = q1, (q1, a3) = q0, (q5, a3) = q4, (q0, a1) = q0, (q1, a2) = q0, (q5, a2) = q1, (q5, a1) = q0, (q3, a3) = q5, (q3, a1) = q1, (q1, a1) = q3, (q4, a3) = q0, (q3, a2) = q2, (q2, a3) = q4, (q0, a3) = q5, (q4, a2) = q0, (q2, a1) = q0, (q2, a2) = q1, (q0, a2) = q1]), q0, [q4, q1]):
transitionGraph(dfa); |
 |
| > | minimalDFA(dfa); |
     |
(5.6.9) |
| > | # L={w \in {a,b}^*:n_a(w) mod 3 > n_b(w) mod 3}
nfa:=mkNFA([q0,q1,q2,q3,q4,q5,q6],[a,b],table([(q0,a)=q1,(q1,a)=q4,(q1,b)={q2},(q2,b)={q3},(q3,b)={q1},(q4,a)={q0},(q4,b)={q5},(q5,b)={q6},(q6,b)={q4}]),q0,[q1,q4,q5]); transitionGraph(nfa); |
   |
 |
| > | dfa:=NFA2DFA(nfa):
transitionGraph(dfa); |
 |
| > | minimalDFA(dfa):
transitionGraph(%); |
 |
Convert from table to function:
Transition Graph
Animation
Simplification