Code Golf: Finite-state machine!
- by Adam Matan
Finite state machine
A deterministic finite state machine is a simple computation model, widely used as an introduction to automata theory in basic CS courses. It is a simple model, equivalent to regular expression, which determines of a certain input string is Accepted or Rejected. Leaving some formalities aside, A run of a finite state machine is composed of:
alphabet, a set of characters.
states, usually visualized as circles. One of the states must be the start state. Some of the states might be accepting, usually visualized as double circles.
transitions, usually visualized as directed arches between states, are directed links between states associated with an alphabet letter.
input string, a list of alphabet characters.
A run on the machine begins at the starting state. Each letter of the input string is read; If there is a transition between the current state and another state which corresponds to the letter, the current state is changed to the new state. After the last letter was read, if the current state is an accepting state, the input string is accepted. If the last state was not an accepting state, or a letter had no corresponding arch from a state during the run, the input string is rejected.
Note: This short descruption is far from being a full, formal definition of a FSM; Wikipedia's fine article is a great introduction to the subject.
Example
For example, the following machine tells if a binary number, read from left to right, has an even number of 0s:
The alphabet is the set {0,1}.
The states are S1 and S2.
The transitions are (S1, 0) -> S2, (S1, 1) -> S1, (S2, 0) -> S1 and (S2, 1) -> S2.
The input string is any binary number, including an empty string.
The rules:
Implement a FSM in a language of your choice.
Input
The FSM should accept the following input:
<States> List of state, separated by space mark.
The first state in the list is the start state.
Accepting states begin with a capital letter.
<transitions> One or more lines.
Each line is a three-tuple:
origin state, letter, destination state)
<input word> Zero or more characters, followed by a newline.
For example, the aforementioned machine with 1001010 as an input string, would be written as:
S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
1001010
Output
The FSM's run, written as <State> <letter> -> <state>, followed by the final state. The output for the example input would be:
S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
ACCEPT
For the empty input '':
S1
ACCEPT
For 101:
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
REJECT
For '10X':
S1 1 -> S1
S1 0 -> s2
s2 X
REJECT
Prize
A nice bounty will be given to the most elegant and short solution.
Reference implementation
A reference Python implementation will be published soon.
