That infamous Hopcroft marble finite automata​
​by Tomas De Camino Beck
In Automata theory the book “Introduction to Automata Theory, Languages, and Computation” by John Hopcroft and Jeffrey Ullman is considered one of the most influential book in Computer Science. I’m currently using it for a masters Automata Theory Course in Costa Rica, and programming with Mathematica.
​
I think one of the most fun exercises out of the book, is this infamous Marble exercise. I think it is both interesting for building a Finite State Machine, but also because it makes a great connection between understanding the behaviour of a physical machine, and its description as a finite state machine, that is, that a physical machine can be described and a language generating automata.
​
My goal here is not to show how to solve the problem, but rather to program de resulting marble machine automata in Mathematica. As a professor I know the value of having students to figure this one out on their own.

The problem

We have a marble machine that is described by the following figure (Taken From Hopcroft and Ullman),
Marbles can be release from
A
or
B
. Variables
x
1
,
x
2
and
x
3
represent gates that direct the marble either to the left or right. When a MArble passes on of those gates, after passing, the gate switches direction. The Idea is to construct a Deterministic Finite Automata (DFA), where only marbles coming out of
D
are considered valid.

The Marble DFA

Not showing how I figure out this DFA, given that,
◼
  • 0 represents a gate open to the left and 1 to the right
    • ◼
  • Gate configuration are written as
    x
    1
    x
    2
    x
    3
    as a sequence of 0 and 1 from
    000-111
    • ◼
  • Bold states indicate final states
    • ◼
  • The initial configuration is 000
    • We have the following transition table,
    State
    Configuration
    MarbleinA
    MarbleinB
    0
    000
    1
    5
    1
    100
    2
    6
    2
    010
    3
    7
    3
    110
    4
    11
    4
    000
    1
    5
    5
    011
    6
    8
    6
    111
    7
    9
    7
    001
    10
    4
    8
    010
    3
    7
    9
    110
    4
    11
    10
    101
    5
    12
    11
    101
    5
    12
    12
    100
    2
    6
    So if you start in state 0 (configuration 000), and insert a marble in
    A
    , you will go to state 1 (configuration 100)

    Code

    In Mathematica the transition function can be defined as an Association,
    In[]:=
    δ=Association[​​{0,"A"}1,​​{0,"B"}5,​​{1,"A"}2,​​{1,"B"}6,​​{2,"A"}3,​​{2,"B"}7,​​{3,"A"}4,​​{3,"B"}11,​​{4,"A"}1,​​{4,"B"}5,​​{5,"A"}6,​​{5,"B"}8,​​{6,"A"}7,​​{6,"B"}9,​​{7,"A"}10,​​{7,"B"}4,​​{8,"A"}3,​​{8,"B"}7,​​{9,"A"}4,​​{9,"B"}11,​​{10,"A"}5,​​{10,"B"}12,​​{11,"A"}5,​​{11,"B"}12,​​{12,"A"}2,​​{12,"B"}6​​];
    The extended transition function (See Hopcroft & Ullman), to process a string in the automata is given by,
    In[]:=
    DeltaHat[δ_,q0_,string_]:=FoldList[δ[{#1,#2}]&,q0,Characters[string]]
    To test whether a string is valid,
    In[]:=
    IsValid[δ_,q0_,qf_List,string_]:=MemberQ[qf,Fold[δ[{#1,#2}]&,q0,Characters[string]]];
    Applying this to the marble machine, for example we want to see how “ABBAB” will move from state to state,
    DeltaHat[δ,0,"ABBAB"]
    Out[]=
    {0,1,6,9,4,5}
    Now we can check if this sequence is valid
    IsValid[δ,0,{4,7,8,9,11,12},"ABBAB"]
    Out[]=
    False

    Graph of the DFA

    I give some explanation of the following code here.
    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[δ]}];
    In[]:=
    UnifyLabels[labels_]:=If[Length[#]>1,First[Keys[#]](Values[#]&/@#),First[#]]&/@GatherBy[labels,First];
    In[]:=
    UnifyEdges[edges_]:=First/@Gather[edges];
    ShowGraph[δ_,s_,q0_,q_List]:=Graph[​​UnifyEdges[ToEdges[δ]],​​VertexSizeLarge,​​VertexLabelsToVertexLabels[s],​​EdgeLabelsUnifyLabels[ToEdgeLabels[δ]],​​VertexStyleJoin[{0White},Map[(#Red)&,q]]​​]
    Applying it to our marble DFA,
    ShowGraph[δ,13,0,{4,7,8,9,11,12}]
    Out[]=

    ¿Valid Strings?

    We can check what kind of strings are accepted, creating Tuples of different length with the alphabet
    Σ{A,B}
    , and testing them,
    testset=StringJoin/@Tuples[{"A","B"},{4}];​​testset〚Flatten[Position[IsValid[δ,0,{4,7,8,9,11,12},#]&/@testset,True]]〛//TableForm

    References

    ◼
  • Hopcroft and Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wesley.