cip labs

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:

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');
$dfa->setState($z0);

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

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

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

//to set zE as a final state
$zE->setFinal(true);
$dfa->setState($zE);

$dfa->setStartingState('z0');

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

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