Deterministic Finite Automaton in PHP

An important area of the theoretical computer science deals with finite automata and languages. We use a finite automaton to detect words of regular languages. The types of grammars that create a language are defined in the CHOMSKY-hierachy (Noam Chomsky). The table below shows the CHOMSKY-hierachy:

no. title
0 recursively enumerable
1 context-sensitive
2 context-free
3 regular

To represent a regular grammar (type 3) you can use for instance a finite automaton. Here we are using a DFA (deterministic finite automaton) to display a regular grammar. A DFA consists of states and the automaton can reach a new state with a edge to another state (states are a kind of nodes or vertexes). Every state has a successor state for all tokens of the input alphabet. This input alphabet is specified:

for this example:

Σ = {a,b,c}

The DFA in the example below accepts all words that contain the sub string ‘abc':


The circle represents a state and the edge represents the input of a token from the input word. The state, which is marked bold, is called the final state. If all tokens of the input word were inputted into the automaton (no token was left) and the automaton is currently in a final state, then the word was accepted from the DFA.

A formal definition of a DFA:

M = (Z, Σ, δ, s0, E)

  • Z… a finite set of states
  • Σ… the input symbols (alphabet)
  • δ… transition function (δ: Q x Σ → Q)
  • s0… start state (s0 ∈ Q)
  • E… a finite set of final states (E ⊆ Q)

The implementation in PHP based on the transition function / transition table of the DFA. The run()-method uses this table to calculate the successor state of every token in every state.
After all tokens are inputted, the run()-method checks, whether the current state is a final state or not. Running run() with true as the second argument, then the function will return the path through the automaton. Using this method with false as second parameter, the return value is boolean (true for success | false for “word isn’t in that language”).


Below you can see the DFA, that accepts only words with an ‘abc’ sub string (from the example), as PHP code:

$dfa = new DFA('test_dfa');

$z0 = new DFA_State('z0');
$z0->setTransition('b', 'z0');
$z0->setTransition('c', 'z0');
$z0->setTransition('a', 'z1');

$z1 = new DFA_State('z1');
$z1->setTransition('b', 'z2');
$z1->setTransition('a', 'z1');
$z1->setTransition('c', 'z0');

$z2 = new DFA_State('z2');
$z2->setTransition('c', 'zE');
$z2->setTransition('b', 'z0');
$z2->setTransition('a', 'z1');

$zE = new DFA_State('zE');
$zE->setTransition('c', 'zE');
$zE->setTransition('b', 'zE');
$zE->setTransition('a', 'zE');

//to set zE as a final state


$result = $dfa->run('accbbababcababa', true);

goto: download (DFA.class.php, DFA_State.php & test.php)

14 thoughts on “Deterministic Finite Automaton in PHP

  1. please send me the DFA.class.php, DFA_State.php & test.php) bcoz the dowload is not happening

  2. Thank you, but the zip file doesn’t look to be correct. It has problem and cannot be extracted.

  3. Fu… Amazing!!!!

    Hey you, who says download doesnt work, get a linux and dump your winshit.

    The download is on TAR.GZ => tar inside a gunzip, so you need to extract the file using winrar on winshits machines, then to the result file change the name to something like and extract again.

    Fu… windows users…

  4. Pingback: cheap nfl jerseys
  5. Even individuals that recognize the Baltimore County seat quite well could not have
    an idea where the Maryland Judo & Jiu-Jitsu Academy
    is located, although Ramos’ program is contiuously developing a reputation for making superior competitors.

Leave a Reply

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