Finite State Automaton implementation

Question

I've been studying compiler construction theory. Right now, I'm studying Finite State Automaton and I've tried to create my own implementation. I'm not sure if my implementation is right.

State machine transition diagram

<?php
/**
 * FINITE STATE AUTOMATON
 * ======================
 * - states
 * - starting state
 * - accept state
 * - transition table
 *
 * Input string examples:
 * 10112 - Accepted
 * 222 - Rejected
 *
 * Diagram: https://i.sstatic.net/DkcIq.png
 */
$s1 = 'S1';
$s2 = 'S2';
$states = [];
$starting_state = $s1;
$transition_table = [
 'S1' => [
 '2' => 'S3',
 '1' => 'S1',
 '0' => 'S2',
 ],
 'S2' => [
 '1' => 'S1',
 '0' => 'S2',
 ],
 'S3' => [],
];
$input_string = '10112';
$current_state = $starting_state;
foreach (str_split($input_string) as $character) {
 if (isset($transition_table[$current_state][$character])) {
 $current_state = $transition_table[$current_state][$character];
 $states[] = $current_state;
 }
}
if (count($states) == strlen($input_string)) {
 echo 'Accepted';
} else {
 echo 'Rejected';
}
echo PHP_EOL;

Did I get the whole idea? Are there something that I've missed?

Is this FSA thing related to regular expressions? It seems to be similar.

Answer 1

It's quite good, I especially like the $current_state explanatory variable. Actually, I'd create another one to remove some duplication:

$transitions = $transition_table[$current_state];
if (isset($transitions[$character])) {
 $current_state = $transitions[$character];
 $states[] = $current_state;
}

Some other notes:

1. The code currently ignores invalid transitions. You could break the loop immediately if a transition is invalid:

   foreach (str_split($input_string) as $character) {
    $transitions = $transition_table[$current_state];
    if (isset($transitions[$character])) {
    $current_state = $transitions[$character];
    $states[] = $current_state;
    } else {
    break;
    }
   }
   

2. Inverting the isset would make the code flatten a little bit:

   foreach (str_split($input_string) as $character) {
    $transitions = $transition_table[$current_state];
    if (!isset($transitions[$character])) {
    break;
    }
    $current_state = $transitions[$character];
    $states[] = $current_state;
   }
   

3. $s2 is unused, I guess you could remove it:

   $s2 = 'S2';
   

4. Are there something that I've missed?

   The linked page mentions classes and I guess it should have been an object oriented solution. Check the Wikipedia article about the Java implementation, it shows a great example.