FOLA-demo15.html

Simplification

> # L={w \in {a,b}^*:n_a(w)>n_b(w)}
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]):

> dfa:=NFA2DFA(nfa);

(5.10.1)

> transitionGraph(dfa);

Plot_2d

> dfa2:=minimalDFA(dfa);

(5.10.2)

> transitionGraph(dfa2);

Plot_2d

> dfa3:=simplifyDFA(dfa2);

$`:=`(dfa3, DFA({_q4, _q2, _q3, _q1, _q0, _q7, _q5, _q6}, {a, b}, TABLE([(_q0, b) = _q2, (_q7, a) = _q2, (_q5, a) = _q2, (_q1, b) = _q6, (_q2, b) = _q2, (_q4, b) = _q3, (_q1, a) = _q2, (_q3, a) = _q6, ...$
$`:=`(dfa3, DFA({_q4, _q2, _q3, _q1, _q0, _q7, _q5, _q6}, {a, b}, TABLE([(_q0, b) = _q2, (_q7, a) = _q2, (_q5, a) = _q2, (_q1, b) = _q6, (_q2, b) = _q2, (_q4, b) = _q3, (_q1, a) = _q2, (_q3, a) = _q6, ...$
$`:=`(dfa3, DFA({_q4, _q2, _q3, _q1, _q0, _q7, _q5, _q6}, {a, b}, TABLE([(_q0, b) = _q2, (_q7, a) = _q2, (_q5, a) = _q2, (_q1, b) = _q6, (_q2, b) = _q2, (_q4, b) = _q3, (_q1, a) = _q2, (_q3, a) = _q6, ...$
$`:=`(dfa3, DFA({_q4, _q2, _q3, _q1, _q0, _q7, _q5, _q6}, {a, b}, TABLE([(_q0, b) = _q2, (_q7, a) = _q2, (_q5, a) = _q2, (_q1, b) = _q6, (_q2, b) = _q2, (_q4, b) = _q3, (_q1, a) = _q2, (_q3, a) = _q6, ...$ (5.10.3)

> transitionGraph(dfa3);

Plot_2d