Nondeterministic Finite Automata in PHP

A few weeks ago, I wrote an article about an implementation of a DFA (deterministic finite automaton) in PHP. Today, I present a implementation for an automaton, that is not deterministic. It means, that the automaton have no, one or more than one edges (for an element from the input alphabet) to an other state. Before I start to give you a launch into how the NFA in PHP works, I give you a short introduction into the theory of nondeterministic finite automata.

To demonstrate an easy example, I use a NFA, that accepts a word, which includes the substring ‘abc’. I used this example also in a previous article (about DFAs). You can compare the following automaton with the DFA that accepts the same words and you would come to the conclusion, that the NFA is easier to build. Thats the truth, but on the other hand, in most (not all) cases the NFA needs more time to execute all simultanous calculations for a token from the alphabet.

An automaton needs (for formal description) an input alphabet. For that example, the alphabet is specified as:

for this example:
Σ = {a,b,c}

A few sentences ago i mentioned, that the NFA needs more time to execute all simultanous calculations. But why? Well, let us choose the input word ‘ccababca’. (For further demonstrations I will use s1, s2, s3 and s4 as names for the states [blue circle] from the left to the right) We start the simulation with the first two tokens ‘cc’. The NFA remains in s1 (state 1). After that the NFA simulates for the token ‘a’. In s1 with input ‘a’ the NFA can go to s2 and can also stay in s1 (self-loop). Here we have the main problem! The NFA simulates all possible calculations and that is the problem, that the NFA has. After token ‘a’ comes token ‘b’ and for that token, the NFA simulates s1 and s3.

The PHP implementation of the NFA works with the transition table of every state. Outward from the starting state(s), the algorithm is looking for a transition from the current state to another – the successor state. After the input word was read, the NFA checks whether it is currently in a final state or not. The formalization of a final state is defined with a thicker border line (as you can see in the sketch above the text). In the PHP implementation it is just a boolean value. You can also choose more than one starting states with:

$nfa = new NFA('test_nfa');
//adding new states
//declare starting states
$nfa->setStartingStates(array('s0','s1'));

The function, explained below, is very important to build NFA’s – but not neccessary. In the code example below, we don’t need this function, therefore it has an own example above.

The code example shows the code fragment, that has the equal functionality as the automaton in the sketch.

require 'NFA.class.php';

$nfa = new NFA('test_nfa');

$s1 = new NFA_State('s1');
$s1->setTransition('b', 's1');
$s1->setTransition('c', 's1');
$s1->setTransition('a', 's2');
$s1->setTransition('a', 's1');
$nfa->setState($s1);

$s2 = new NFA_State('s2');
$s2->setTransition('b', 's3');
$nfa->setState($s2);

$s3 = new NFA_State('s3');
$s3->setTransition('c', 's4');
$nfa->setState($s3); 

$s4 = new NFA_State('s4');
$s4->setTransition('c', 's4');
$s4->setTransition('b', 's4');
$s4->setTransition('a', 's4');
$s4->setFinal(true);
$nfa->setState($s4);

$nfa->setStartingState('s1');

if($nfa->run('accbbababcababa'))
  echo "NFA accepts the input word!";
else
  echo "NFA doesn't accept the input word!";

As you can see in this example, the NFA equals a pattern matcher. With a regular expression parser you are able to build small NFA’s for every part of this expressions. After that you can concatenate this automatons to an automaton, that accepts your complete expression.

You can download the source files here. (NFA.class.php, NFA_State.class.php and test.php)

93 thoughts on “Nondeterministic Finite Automata in PHP

  1. Hello there! Do you knolw if they make any plugins to protect aganst hackers?
    I’m kinda paranoid about losing everything I’ve worked hard on.
    Anyy recommendations?

  2. Amongst flat-tops (equipments without a meter which maintains increasing), the overall
    chances are normally similar regardless of just how high the prize is.

  3. You’ll learn how to recognize trading options, just how to moment industry (aka wise betting), so when to take profits
    or close a.

  4. My brother recommended I would possibly like this blog.
    He was totally right. This put up actually made my day.
    You cann’t imagine simply how so much time
    I had spent for this information! Thank you!

  5. Hi, I do think this is an excellent web site. I stumbledupon it I may return yet again since i have saved as a favorite it.
    Money and freedom is the greatest way to change,
    may you be rich and continue to help other people.

Leave a Reply

Your email address will not be published. Required fields are marked *