Location: PHPKode > scripts > DEA classes > dea-classes/class_dea.inc
<?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;
        }
	}
}
?>
Return current item: DEA classes