<?php
/**
* defining the "empty word" (or neutral element, however)
* @var string µ(mu);
*/
//#########################################################################
define("µ", "");
//#########################################################################
// 0 = no debug
// 1 = debug transitions
// 2 = debug constructor
// 4 = debug transitions build from File
// ..to get the desired msgs. , simply add the above mentioned powers
//#########################################################################
$DEBUG = 0;
//#########################################################################
/**
* class DEA
*
* representing an deterministic-finite-automata
*
* @see subclass::method()
*/
//#########################################################################
class DEA {
//#########################################################################
/**
* constructor DEA
* call $myDEA = new DEA( array[int+] states,
* array[chr(1)] termsymbols,
* array[int+][chr(1)] delta_states,
* int+ start_state,
* array[int+] final_states );
* @return DEA
*/
//#########################################################################
function DEA( $Q = null, $S = null, $delta = null, $qS = null, $qF = null ) {
//#########################################################################
global $DEBUG;
if ( $Q && $S && $delta && $qS && $qF ) {
$this->states = $Q;
if ($DEBUG & pow(2,1) ) { echo "DEA::DEA() got ".count($Q)." states<br>\n"; }
$this->termsymbols = $S;
if ($DEBUG & pow(2,1) ) { echo "DEA::DEA() got ".count($S)." terminal symbols<br>\n"; }
$this->delta_states = $delta;
if ($DEBUG >= pow(2,1) ) {
echo "DEA::DEA() got ";
$entries = 0;
$rowCount = count( $delta );
echo $rowCount." rows<br>\n";
for( $y=0; $y < $rowCount; $y++ ) {
$colCount = count( $delta[$y] );
echo $colCount." cols<br>\n";
foreach ( $this->termsymbols as $ichar ) {
echo "....".$delta[$y][$ichar]." content<br>\n";
// count all entries greater than 0,
if ( $delta[$y][$ichar] >= 0 ) { ++$entries; }
}
echo $entries."<br>\n";
}
echo $entries." states-transitions<br>\n";
}
$this->start_state = $qS;
if ($DEBUG & pow(2,1) ) { echo "DEA::DEA() got ".count($qS)." start states[".$qS[0]."]<br>\n"; }
$this->final_states = $qF;
if ($DEBUG & pow(2,1) ) { echo "DEA::DEA() got ".count($qF)." final states[".$qF[0]."]<br>\n"; }
}
}
/**
* array states
* @var array states
*/
//#########################################################################
var $states = array();
//#########################################################################
/**
* array termsymbols
* @var array termsymbols
*/
//#########################################################################
var $termsymbols = array();
//#########################################################################
/**
* int start_state
* default is 0
*
* @var int start_state
*/
//#########################################################################
var $start_state = 0;
//#########################################################################
/**
* array end states
* default is 0
*
* @var array end states
*/
//#########################################################################
var $final_states = array();
//#########################################################################
/**
* array delta states
* States X TermSyms -> State
* default is 0
*
* @var int delta state
*/
//#########################################################################
var $delta_states = 0;
//#########################################################################
/**
* transform( q, x ) => @return newState
* @return int newState
*/
//#########################################################################
function _delta( $delta_states, $state = '', $input = '' ) {
//#########################################################################
global $DEBUG;
//if we have a valid input, then...
if ( ! ($state >= 0) && $input ) { return µ; }
/*
*####
* WAY ONE -- complex ( max.costs. = O[ |states|*|termsyms| ] )
* ####
*
// ...search all entries in delta_states with our actual state and input
foreach ( $delta_states as $istate ) {
foreach ( $istate as $iterm => $nstate ) {
if ( $istate == $state ) {
if ( $iterm == $input) {
return $nstate;
}
}
}
}
* ####
* WAY TWO -- direct ( costs. = O[ 1 ] )
* ####
*/
if ($DEBUG & pow(2,0) ) {
echo "<br>DEA::delta( ".$state." , ".$input.") => [".$delta_states[$state][$input]."]<br>\n";
//var_dump( $state );
return $delta_states[ $state ][ $input ];
} else {
// if we land here, we haven't found a corresponding pair
// of ( state, term ) in our list ( delta_states )
// so put out the empty word, we have no answer to this query
return µ;
}
}
/**
* transform( q, x ) => @return newState
*
* @param int state
* @param string input
*
* @return mixed
*/
//#########################################################################
function delta( $state = '', $input = '' ) {
//#########################################################################
// if we have a input word longer than 1, call it recursively
if ( strlen( $input ) > 1 ) {
return $this->delta( $this->_delta( $this->delta_states, $state, $input{0} ),
substr($input, 1) );
} else {
return $this->_delta( $this->delta_states, $state, $input );
}
}
/**
* check whether we have reached a final state yet
*
* @param int state
*
* @return boolean
*/
//#########################################################################
function isEndState( $state = '' ) {
//#########################################################################
if ( in_array( $state, $this->final_states)) {
return true;
} else {
return false;
}
}
/**
* check whether the given word is accepted (at the end of work we are in a final state)
*
* @param string word
*
* @return boolean
*/
//#########################################################################
function accept( $word = '' ) {
//#########################################################################
if ( $this->isEndState( $this->delta( $this->start_state[0], $word ) ) ) {
return true;
} else {
return false;
}
}
/**
* This function adds a Transition to the automata (existing edges will be overwritten!)
*
* @param int actual_state
* @param str(1) symbol
* @param int resulting_state
*
* @return void
*/
//#########################################################################
function addTransition( $q, $a, $nq ) {
//#########################################################################
global $DEBUG;
if ($DEBUG & pow(2,2) ) { echo "<br> Trans: [ (".$q."), (".$a.") ] ==> [ (".$nq.") ]<br>\n"; }
// if we haven't this state in our set, add it!
if ( ! in_array( $q, $this->states ) ) {
array_push( $this->states, $q );
//sort array
}
// if we haven't this termsymbol in our set, add it!
if ( ! in_array( $a, $this->termsymbols ) ) {
array_push( $this->termsymbols, $a );
//sortier arr
}
// if we haven't this (n+1)-state in our set, add it!
if ( ! in_array( $nq, $this->states ) ) {
array_push( $this->states, $nq );
//sortier arr
}
// fetch perhaps existing transitions
$existingTrans = $this->delta_states[$q];
// do we've a valid already existing
if ( is_array($existingTrans) ) {
// we already a exact-match transition
// ( [now_q, symbol] => next_q ), unfortunately overwrite it!
$existingTrans[ $a ] = $nq;
}
else {
// okay, construct a valid transition-entry: array( q, a, nq )
$existingTrans[ $a ] = $nq;
// ...why do i here scan through all termsymbols...???
// ...-> ?check whether symbol is in termsymbol-set?
/*
foreach ( $this->termsymbols as $symbol ) {
if ( $symbol == $a ) {
$existingTrans[ $symbol ] = $nq;
} else {
$existingTrans[ $symbol ] = $q;
}
}*/
}
// finally add it to internal object-array
$this->delta_states[$q] = $existingTrans;
/*echo "<br>Matrix [$q][$a] auf $nq<br>\n";
var_dump( $this->delta_states);
echo "<br><br>\n";*/
}
/**
* build the transition-table ( delta-func of automata) from file
* this function expect a text file like this...
*<code>
* 0:a:1[eol]
* 0:b:3[eol]
* 1:a:2[eol]
* 1:b:0[eol]
* 2:a:3[eol]
* 2:b:1[eol]
* 3:a:0[eol]
* 3:b:2[eol]
* [eof]
*</code>
*
* ...will recognize the language(all accepted words)
* L:={ w | count_of_a_in_(w)-count_of_b_in_(w)= 3 (mod 4) }
*
* @param string filename
*
* @return boolean (true, if all okay(path,file,perm,syntax) otherwise false)
*/
//#########################################################################
function readDeltafromFile( $filename = '' ) {
//#########################################################################
global $DEBUG;
// initial settings && temp_vars
$tmp = null;
$tmpQ = $this->delta_states;
$tmpS = $this->termsymbols;
$this->delta_states = array();
$this->termsymbols = array();
// if func::file() results no error, go on!
if ( $tmp = file( $filename ) ) {
// read the file line per line..
foreach ( $tmp as $row ) {
// seperate a line with a ':'
$tmp0 = explode(':', $row);
// if #tokens = 3, everything is good!
if ( count($tmp0) == 3 ) {
// ..call addTransition() and remove control-chars
$this->addTransition( $tmp0[0], $tmp0[1], ereg_replace( "\t|\n|\r", '', $tmp0[2] ));
}
}
if ($DEBUG & pow(2,2) ) { echo "DEA::readDeltafromFile() got ".count($this->states)." states<br>\n"; }
if ($DEBUG & pow(2,2) ) { echo "DEA::readDeltafromFile() got ".count($this->termsymbols)." terminal symbols<br>\n"; }
return true;
}
// ..a unkown file error occured, permissions?, file_existent?, binary_file?
else {
if ($DEBUG & pow(2,1) ) {
echo "DEA::readDeltafromFile() ERROR occured while tried to read text-file ".$filename."<br>\n";
}
return false;
}
}
}
?>