<?
/*
This example will use define a DFA to accept all strings on {0,1} that includes 001
Example of accepted strings: 001 , 1001 , 11001 , 10100101 , 1010011101
Example of not accepted strings: 0100 , 1010 , 010101010100
The class should be provided with 3 arrays.
1) States
2) Alphabet
3) Transition
Alphabet
is just a simple array consists of alphabets used for this machine.
States
is simple array too, but with the difference that each item point to a value ("Qs"=>"start"). The first is the name of the state, and the second ("start") is the type of this state.
each 'States array' should consist of at least 1 start and 1 final item.
Transition
This array will tell the automaton where to go.
Consider this:
$transition["Qs"]=array("0"=>"Q0","1"=>"Qs");
If current start is 'Qs', and the machine sees 0, it will go to Q0 state and if the machine sees 1, it will go to Qs state again.
How does it work?
The automaton will start from the start state, and read 1 character from the input and go to another state according to transition array.
Once it reaches the end of the input, it will stop and check the current state. if current state is final, then it returns true, otherwise, it will return false.
*/
require_once("dfa.class.php");
$alphabet=array("0","1");
$states=array(
"Qs"=>"start",
"Q0"=>"none",
"Q00"=>"none",
"Q001"=>"final"
);
$transition=array();
$transition["Qs"]=array("0"=>"Q0","1"=>"Qs");
$transition["Q0"]=array("0"=>"Q00","1"=>"Qs");
$transition["Q00"]=array("0"=>"Q00","1"=>"Q001");
$transition["Q001"]=array("0"=>"Q001","1"=>"Q001");
$myDFA=new DFA($states,$alphabet,$transition);
if ($myDFA->accept("10101010011101")) {
echo "Accepted!";
}else{
echo "NOT Accepted!--";
echo $myDFA->show_error();
}
?>
|
Stumble It!
Bookmark in del.icio.us
Download
