Modified finite automata simulation with improved graphs​
​by Tomas De Camino Beck
I’m currently teaching a Masters level Automata Theory course, and I want to make it a bit more hands on (since we are virtual...). While looking for people using Mathematica, I was surprised that I could not find much code out there. I did find this post on this community
Simulating Finite Automata (and making it look nice)
​https://community.wolfram.com/groups/-/m/t/1611589​
which I enjoyed, but I wanted to make something a bit more closer to theory, and with a “cleaner” code.

Definitions

A finite state machine is an abstract mathematical structure. It is a 5-tuple
(Q,Σ,δ,
q
0
,F)
, where,
◼
  • Q
    is a finite set of states
    • ◼
  • Σ
    is a finite set of symbols (alphabet)
    • ◼
  • δ:QΣQ
    , is a transition function. For this one we will use Associations in Mathematica
    • ◼
  • A start state
    q
    0
    ∈Q
    • ◼
  • A set of final states
    F⊆Q
    • For practical purposes, in Mathematica
    Q{0,1,2,…}
    , and we will define a transition function as Associations[{q,x}q’,...], where q, q’ are states and x is a character (so Head[x] = String)

    "Running" a finite state machine

    Consider the following state transition definition:
    In[]:=
    δ=Association[​​{0,"1"}1,​​{0,"0"}0,​​{1,"0"}0,​​{1,"1"}2​​];
    It is a 2 state machine, that takes characters “0” and “1”. To “apply” this automata, we define the following function in Mathematica:
    In[]:=
    ApplyAutomata[δ_,q0_,string_]:=FoldList[(δ[{#1,#2}])/._Missing0&,q0,Characters[string]]
    Notice how we apply the function FoldList, to recursively “move” form state to state, depending on the current string input. we capture undefined transitions, identifying Missing functions that are returned if an association does not contain a particular Key. Applying to the previous
    δ
    definitions, with 0 as the starting state,
    ApplyAutomata[δ,0,"01110101"]
    Out[]=
    {0,0,1,2,0,0,1,0,1}
    We are interested to know if a string is valid. If in our previous example 2 is a final state “01110101” does not finish in that state so that string is NOT accepted by this automata. We can build a function for this,
    In[]:=
    IsValidQ[δ_,q0_,string_,qf_]:=Fold[(δ[{#1,#2}])/._Missing0&,q0,Characters[string]]qf;​​IsValidQ[δ_,q0_,string_,qf_List]:=MemberQ[qf,Fold[(δ[{#1,#2}])/._Missing0&,q0,Characters[string]]];
    It is very similar to ApplyAutomata[], but we want to check if the final state reached belongs to the set of final states. So,
    IsValidQ[δ,0,"01110101",2]
    Out[]=
    False
    A valid one,
    IsValidQ[δ,0,"011",2]
    Out[]=
    True

    Building a graph representation

    Creating a graph function based on the state transitions
    δ
    , requires converting rules to Directededges[] and to create the corresponding labels for arcs.
    In[]:=
    ToEdges[δ_]:=MapThread[DirectedEdge,{First/@Keys[δ],Values[δ]}];​​ToVertexLabels[s_]:=Table[Rule[i-1,Placed[i-1,Center]],{i,1,s}];​​ToEdgeLabels[δ_]:=MapThread[Rule,{ToEdges[δ],Last/@Keys[δ]}];
    So we don’t draw double arcs, we have also to unify,
    In[]:=
    UnifyLabels[labels_]:=If[Length[#]>1,First[Keys[#]](Values[#]&/@#),First[#]]&/@GatherBy[labels,First];
    In[]:=
    UnifyEdges[edges_]:=First/@Gather[edges];
    Now we define a graph function,
    ShowGraph[δ_,s_,q0_,q_List]:=Graph[​​UnifyEdges[ToEdges[δ]],​​VertexSizeLarge,​​VertexLabelsToVertexLabels[s],​​EdgeLabelsUnifyLabels[ToEdgeLabels[δ]],​​VertexStyleJoin[{0White},Map[(#Red)&,q]]​​]
    As you can see the function ShowGraph[δ_,s_,q0_,q_List], takes the transition function
    δ
    , since we are labeling states from 0 onward, we need to define how many states
    s
    the machine has, the initial state, and the set of final states. Initial states nodes are filled white, and final states red. With the previous example,
    ShowGraph[δ,3,0,{2}]
    Out[]=
    A nice example taken from Sipser Book (See references)
    In[]:=
    δ=Association[​​{0,"a"}1,​​{0,"b"}3,​​{1,"a"}1,​​{1,"b"}2,​​{2,"b"}2,​​{2,"a"}1,​​{3,"b"}3,​​{3,"a"}4,​​{4,"b"}3,​​{4,"a"}4​​];
    This state machine accepts strings that start and finish with “a”, or start and finish with “b”. So for example
    IsValidQ[δ,0,"bb",{1,3}]
    Out[]=
    True
    Is a valid string, but,
    IsValidQ[δ,0,"bba",{1,3}]
    Out[]=
    False
    Not
    The corresponding graph,
    ShowGraph[δ,5,0,{1,3}]
    Out[]=

    References

    ◼
  • Michael Sipser, Introduction to theTheory of Computation. PWS Publishing Company, 2006.