Wolfram Research

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 NFAPlot, as {currentstate, input}{newstate(s)}.
The alphabet, accept states and input should be given as lists.

Examples

Basic Examples

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

ResourceFunction["NFAPlot"] can illustrate the NFA before simulation:

In[4]:=
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]=

Resource History

See Also

License Information