Time for non-deterministic finite automata​
​by Tomás de Camino Beck

Introduction

Non-deterministic automata are a special type of automata where the exact state to which the machine moves cannot be determined. In practical terms, it means that the transition from state to state with a particular symbol, can take us to many different states, not only one. I talked about deterministic automata (DFA) on this post, here I focus on Non-deterministic automata. Formally we define a Non-Deterministic Finite Automata (NFA) as
N(Q,Σ,δ,
q
0
,F)
where:
◼
  • Q
    is a finite set of states
    • ◼
  • Σ
    is a finite set of symbols (alphabet)
    • ◼
  • δ:QΣ
    Q
    2
    . Here is where the difference comes with respect to a DFA. The transitions functions maps to a set of states instead of one state only
    • ◼
  • A starting state
    q
    0
    ∈Q
    • ◼
  • A set of final states
    F⊆Q

    • Working with NFA in Mathematica

    Les use the following NFA as an example (taken from Hopcroft),
    This automata accepts strings that end in 01. We use associations to build the transitions function. Keep in mind that we want to define them as
    δ:QΣ
    Q
    2
    , so:
    In[]:=
    δ=Association[​​{0,"0"}{0,1},​​{0,"1"}{0},​​{1,"1"}{2}​​];
    Notice how the keys map to a list of states, instead of a state.​​​​Now lets build a functions for processing a string with this transitions function, and lets do it step by step. Mathematically we want to create an extended
    
    δ
    function, the following way,
    ◼
  • Base step:
    
    δ
    (q,ϵ){q}
    • ◼
  • Inductive step: let
    wxa
    and
    
    δ
    (q,x){
    p
    1
    ,
    p
    2
    ,…,
    p
    k
    }
    , then we have that
    
    δ
    (q,w)
    k
    ⋃
    i1
    δ(
    p
    i
    ,a)
    • You can check Hopcroft’s book for a more detailed explanation.
    As a start, based on the mathematical definition, we have to evaluate
    δ
    recursively. For that, we can use FoldList. For example,
    FoldList[δ[{#1,#2}]&,0,{"1"}]
    Out[]=
    {0,{0}}
    Now we have to deal with the fact that
    δ
    returns a list, and each one of those have to be evaluated. We have to modify the pure function δ[{#1,#2}]& that we are using in FoldList. So for example if we have to evaluate states {0,1} with symbol “1”, we can do,
    Table[δ[{#1[[i]],#2}],{i,Length[#1]}]&[{0,1},"0"]
    Out[]=
    {{0,1},Missing[KeyAbsent,{1,0}]}
    Now lets deal with missing transitions. With the same example we can then write,
    Table[δ[{#1[[i]],#2}]/._MissingNothing,{i,Length[#1]}]&[{0,1},"0"]
    Out[]=
    {{0,1}}
    Basically we get rid of missinng keys. Now, we want the union of all resulting states,
    Union@@Table[δ[{#1[[i]],#2}]/._MissingNothing,{i,Length[#1]}]&[{0,1},"0"]
    Out[]=
    {0,1}
    Finally we are ready to create our
    
    δ
    function DeltaHat,
    In[]:=
    DeltaHat[δ_,q0_List,string_]:=FoldList[Union@@Table[δ[{#1[[i]],#2}]/._MissingNothing,{i,Length[#1]}]&,q0,Characters[string]]
    We can now use it to evaluate the string “00101” for example,
    DeltaHat[δ,{0},"00101"]
    Out[]=
    {{0},{0,1},{0,1},{0,2},{0,1},{0,2}}
    Now we can create a function that determines is a string is valid,
    In[]:=
    IsValid[δ_,q0_List,qf_List,string_]:=IntersectingQ[Last[DeltaHat[δ,q0,string]],qf]
    IsValid[δ,{0},{2},"00101"]
    Out[]=
    True
    Enjoy!

    References

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