Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
Automata Package
Automata supports computation with finite state machines, syntactic semigroups and one-dimensional cellular automata. There are some 250 functions in the package, we only mention a few of them below. For more information and more examples, see .
Finite State Machines
Formatting
Formatting
By default, formatting of finite automata is turned off. In particular for large automata it is usually preferable to turn formatting on.
In[7]:=
Needs["KlausSutner`Automata`"]
In[46]:=
M=
"a",-3,
[2]
 | PositionFA |
 | Alpha |
Out[46]=
FATSys4,2,
,Alpha[2,],TransTypeNFA,AccCondExistential[{1},{4}]
In[47]:=
FormatFA[]M
Out[48]=
FA
 |  |
| ||||
In[49]:=
M//
 | PlotFA |
Out[49]=
The situation for semigroups is similar.
In[50]:=
MM=
[M]
| DeterminizeFA |
Out[50]=
FA
|  |
| ||||
In[53]:=
sg=
[MM]
| SemigroupGenerate |
 | SemigroupGenerators |
Out[53]=
Semigroup[{SGT[{2,3,5,7,5,7,3,2}],SGT[{1,4,6,8,6,8,4,1}],SGT[{3,5,5,3,5,3,5,3}],SGT[{4,6,6,4,6,4,6,4}],SGT[{2,7,7,2,7,2,7,2}],SGT[{1,8,8,1,8,1,8,1}],SGT[{5,5,5,5,5,5,5,5}],SGT[{6,6,6,6,6,6,6,6}],SGT[{7,7,7,7,7,7,7,7}],SGT[{8,8,8,8,8,8,8,8}],SGT[{3,3,3,3,3,3,3,3}],SGT[{4,4,4,4,4,4,4,4}],SGT[{2,2,2,2,2,2,2,2}],SGT[{1,1,1,1,1,1,1,1}]},Generators{SGT[{2,3,5,7,5,7,3,2}],SGT[{1,4,6,8,6,8,4,1}]},Witnesses{a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb},Equations{aaaaaaa,aaabaab,aabaaba,aabbabb,abaabaa,ababbab,abbabba,abbbbbb,baaaaaa,baabaab,babaaba,babbabb,bbaabaa,bbabbab,bbbabba,bbbbbbb}]
In[54]:=
FormatSemigroup[]
In[55]:=
sg
Out[55]=
Semigroup
|  |
| ||||
Lastly, there is the problem of making the empty string visible. Automata uses a alternative symbol Eps for the empty string. To make this look better, one can format Eps.
In[61]:=
| Words |
| Alpha |
Out[61]=
{Eps,a,b,aa,ab,ba,bb}
In[62]:=
| FormatEps |
In[64]:=
| Words |
| Alpha |
| WordLength |
Out[64]=
{ϵ,a,b,aa,ab,ba,bb}
Out[65]=
{0,1,1,2,2,2,2}
Formatting Eps may cause problems when the input to certain function involves Eps. For extensive computations it is best to turn ϵ-formatting off.
| FormatEps |
Machine Constructions
Machine Constructions
Define a 2-letter alphabet for use in various machine constructions below.
In[9]:=
A2=
[2];Through
,
[A2]
| Alpha |
| AlphabetList |
| AlphabetCount |
Out[10]=
{{a,b},2}
We construct a partial DFA (deterministic but incomplete) accepting a finite language using a quotient construction.
In[194]:=
pdfa=
[{"aaa","bbb","aabb"},A2]
| FiniteLanguageFA |
Out[194]=
FA
|  |
| ||||
Sampling the language of the automaton shows that the machine works as expected.
In[195]:=
| LanguageFA |
| SizeOnly |
| LanguageFA |
Out[195]=
{0,0,0,2,1,0,0,0,0,0,0,0,0}
Out[196]=
{{},{},{},{aaa,bbb},{aabb},{},{},{},{},{},{}}
We can visualize the machine as a edge-labeled directed graph.
In[208]:=
| PlotFA |
Out[208]=
For small alphabets, it is often preferable to use colors instead of edge labels.
In[197]:=
| PlotFA |
| Type |
Out[197]=
For a PDFA, determinization simply adds a sink. In this case, we obtain a non-minimal DFA.
In[203]:=
dfa=
[pdfa]
| DeterminizeFA |
Out[203]=
FA
| |
| ||||
By default, the plotting function displays only the trim part of the automaton.
Minimization collapses some of the states and produces a DFA of size 7.
The machines are all equivalent (the equivalence test does not use minimization).
The construction of the PDFA is based on a simple trie, alternatively we can use a quotient construction (which is inefficient for large sets of words).
The quotient construction ensures that the automaton is already minimal.
The machine works as advertised for words of length 6:
Here are two mod-counters for plain factors and their intersection.
The constructor for semilinear machines generally produces non-minimal machines, as a result our counter is larger than needed.
It is often useful to preserve state sets during certain operations.Minimization produces a new automaton whose states are naturally sets of states of the old automaton.
Thus, the states 1, 7, 8 are behaviorally equivalent in sl12.
Another operation where structured state sets are often useful is determinization, based on the standard Rabin-Scott construction.
On occasion, one may want to preserves states several levels deep. Here is de Bruijn type DFA with a naturally structured state set: the states are all words up to length 4.
Preserving state sets under minimization can be helpful to understand the structure of a machine.
One can directly see how behaviorally equivalent states are collected.
In this case, converting back produces the original automaton.
By insisting that the back transitions lead to the same branch, rather than just nodes constructed earlier in the process, we get a larger frontier automaton.
The picture obscures the tree structure, but it can be recovered as follows.
The machines are duly equivalent.
Regular Expressions
Regular Expressions
A regular expression for the language "even number of a, even number of b".
The default conversion in general produces a machine with ϵ-transitions.
Eliminating the ϵ-transitions adds a few more letter-transitions.
Determinization yields a machine on 8 states.
Lastly, the minimal automaton.
Another example, a regular expression that recognizes numbers that are divisible by 3, written in binary, MSD first, with leading zeros. It is convenient to switch the default alphabet for regular expressions to the corresponding digit alphabet.
Our presentation allows for leading zeros.
Check the corresponding numerical values
All the machines that appear during the conversion process.
The growth function is easy to find in this case.
Syntactic Semigroups
The corresponding semigroup has 14 elements and is of degree 8, the state complexity of M.
The Cayley table of this semigroup.
The resulting data structure also maintains information about witnesses and equations.
A table of semigroup elements with various special properties.
The witnesses for the right nulls are all words of length 3.
The equations remove the first letter of all length 4 words, so this is consistent.
Transformation DFA
Transformation DFA
The transformation semigroup of a DFA can be turned into another DFA whose states are the elements of the semigroup. The new automaton is potentially much larger and covers the original machine. First, an example with modest increase in size.
A 3-state DFA can generate the full transformations semigroup of degree 3,
Cellular Automata
De Bruijn Automaton
De Bruijn Automaton
Two orbits of elementary cellular automaton number 45, on a two-point seed and on a random configuration.
Surjectiveness on infinite configurations implies surjectiveness on infinitely many finite configurations by a compactness argument (using cyclic boundary conditions). The corresponding de Bruijn automaton is unambiguous.
We can find all ECA with surjective global map by checking universality of these de Bruijn automata (but beware exponential blowup for cellular automata of larger width).
So there are 2 limit cycle of length 24, 3 of length 6, and so on.
Fischer Automata
Fischer Automata
Since this language is always factorial, extensible and transitive, there is a better minimal automaton for this language, obtained as follows.
The minimal DFA here has maximal size 16.
A deterministic and reduced semiautomaton for the cover language can be determined by finding a terminal strongly connected component in the minimal DFA for the language (which component is uniquely determined). Here is a function that computes this minimal Fischer automaton.
The minimal Fischer automaton for ECA 210 looks like so.
It has only one strongly connected component.