Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
KlausSutner`Automata`Fsm`
RegexToNNFA  |
| RegexToNNFA[reg] converts regular expression reg into a McNaughton-Yamada automaton. | |
Examples
(1)
Basic Examples
(1)
Converting a regular expression for the even/even parity language over alphabet .
{a,b}
In[1]:=
e0=
["aa","bb"];e1=
["ab","ba"];e00=
e0,
e1,
[e0],e1
 | REP |
| REP |
 | RES |
| REP |
 | RET |
 | RES |
Out[1]=
RES[REP[REP[aa,bb],RET[REP[ab,ba],RES[REP[aa,bb]],REP[ab,ba]]]]
Convert the expression in stages to a minimal DFA.
In[2]:=
nnfa=
[e00]
| RegexToNNFA |
Out[2]=
NNFA[16,{{1,2},{2,1},{2,3},{2,5},{2,7},{3,4},{4,1},{4,3},{4,5},{4,7},{5,6},{6,9},{6,11},{6,13},{6,15},{7,8},{8,9},{8,11},{8,13},{8,15},{9,10},{10,9},{10,11},{10,13},{10,15},{11,12},{12,9},{12,11},{12,13},{12,15},{13,14},{14,1},{14,3},{14,5},{14,7},{15,16},{16,1},{16,3},{16,5},{16,7}},{1,1,2,2,1,2,2,1,1,1,2,2,1,2,2,1},{1,3,5,7},{2,4,14,16},1]
In[3]:=
M1=
nnfa,
[2]
| NNFAToFA |
 | Alpha |
Out[3]=
FA
 |  |
| ||||
In[4]:=
| MinimizeFA |
 | PlotFA |
Out[4]=
 |
|
 |
|
 |
|
""