Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 NFASimulation

Source Notebook

Simulate the behavior of a nondeterministic finite automaton

Contributed by: Katja Della Libera

ResourceFunction["NFASimulation"][rules,alphabet,start,accept,input]

simulates the finite automaton described by rules, alphabet, start and accept over input.

Details and Options

Rules can be specified similarily to the format in TuringMachine or the resource function NFAPlot, as {currentstate, input}→{newstate(s)}.
The alphabet, accept states and input should be given as lists.

Examples

Basic Examples (3) 

A simple NFA that rejects the given input:

In[1]:=
ResourceFunction[ "NFASimulation"][{{0, 1} -> {1}, {0, 0} -> {2}, {1, 1} -> {2}, {1, 0} -> {0}, {2, 1} -> {0}, {2, 0} -> {1}}, {0, 1}, 0, {2}, {1, 1, 1, 0, 0, 0}]
Out[1]=

If the last state is in the list of accept states, the input is accepted:

In[2]:=
ResourceFunction[ "NFASimulation"][{{0, 1} -> {1}, {0, 0} -> {2}, {1, 1} -> {2}, {1, 0} -> {0}, {2, 1} -> {0}, {2, 0} -> {1}}, {0, 1}, 0, {2, 0}, {1, 1, 1, 0, 0, 0}]
Out[2]=

If one of the letters in the input is not in the alphabet, the simulation will throw an error:

In[3]:=
ResourceFunction[ "NFASimulation"][{{0, 1} -> {1}, {0, 0} -> {2}, {1, 1} -> {2}, {1, 0} -> {0}, {2, 1} -> {0}, {2, 0} -> {1}}, {0, 1}, 0, {2, 0}, {1, 1, 1, 0, 0, 0, 2}]
Out[3]=

Scope (1) 

The resource function NFAPlot can illustrate the NFA before simulation:

In[4]:=
ResourceFunction[ "NFAPlot"][{{0, "1"} -> {1}, {0, "0"} -> {4}, {1, "1"} -> {1}, {1, "0,1"} -> {2}, {2, "0"} -> {2}, {2, "1"} -> {3}, {3, "0,1"} -> {4}, {4, "0,1"} -> {4}}, 0, {4}, "StateLabelSize" -> Medium]
Out[4]=
In[5]:=
ResourceFunction[ "NFASimulation"][{{0, "1"} -> {1}, {0, "0"} -> {4}, {1, "1"} -> {1, 2}, {1, "0"} -> {2}, {2, "0"} -> {2}, {2, "1"} -> {3}, {3, "0"} -> {4}, {3, "1"} -> {4}, {4, "0"} -> {4}, {4, "1"} -> {4}}, {"0", "1"}, 0, {4}, {"1", "1", "0", "0", "1", "1"}]
Out[5]=

Version History

  • 1.0.0 – 03 July 2019

Related Resources

License Information