Code Golf: Finite-state machine!
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) -> S1and(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
Note: Following your comments, the S1 line (showing the first state) might be omitted, and the following output is also acceptable:
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 250 rep bounty will be given to the shortest solution.
Reference implementation
A reference Python implementation is available here. Note that output requirements have been relaxed for empty-string input.
Addendum
Output format
Following popular demand, the following output is also acceptable for empty input string:
ACCEPT
or
REJECT
Without the first state written in the previous line.
State names
Valid state names are an English letter followed by any number of letters, _ and digits, much like variable names, e.g. State1, state0, STATE_0.
Input format
Like most code golfs, you can assume your input is correct.
Summary of answers:
- Cobol - 4078 characters
- Python - 171 characters, 568 characters, 203 characters, 218 characters, 269 characters
- sed - 137 characters
- ruby - 145 characters, 183 characters
- Haskell - 192 characters, 189 characters
- LISP - 725 characters
- Perl - 184 characters
- Bash - 184 characters
- Rexx - 205 characters
- Lua - 356 characters
- F# - 420 characters
- C# - 356 characters
- Mixal - 898 characters
The sed 137 solution is the shortest, ruby 145 is #2. Currently, I can't get the sed solution to work:
cat test.fsm | sed -r solution.sed
sed -r solution.sed test.fsm
both gave me:
sed: -e expression #1, char 12: unterminated `s' command
so unless It there are clarifications the bounty goes to the ruby solution.
Answer
Python 2.7+, 201 192 187 181 179 175 171 chars
PS. After the problem was relaxed (no need to output state line on empty input), here is new code that's notably shorter. If you are on version <2.7, there is no dict comprehension, so instead of {c+o:s for o,c,s in i[1:-1]} try dict((c+o,s)for o,c,s in i[1:-1]) for the price of +5.
import sys
i=map(str.split,sys.stdin)
s=i[0][0]
for c in''.join(i[-1]):
if s:o=s;s={c+o:s for o,c,s in i[1:-1]}.get(c+s,());print o,c,'->',s
print'ARCECJEEPCTT'[s>'Z'::2]
And its test output:
# for empty input
ACCEPT
# for input '1001010'
S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
ACCEPT
# for input '101'
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
REJECT
# for input '10X'
S1 1 -> S1
S1 0 -> s2
s2 X -> ()
REJECT
# for input 'X10'
S1 X -> ()
REJECT
Previous entry (len 201):
import sys
i=list(sys.stdin)
s=i[0].split()[0]
t={}
for r in i[1:-1]:a,b,c=r.split();t[a,b]=c
try:
for c in i[-1]:print s,c.strip(),;s=t[s,c];print' ->',s
except:print('ACCEPT','REJECT')[s>'Z'or' '<c]
I want to apologize before someone slaps me for it: the code behavior is slightly different from the original spec - per question-comments discussion. This is my illustration for the discussion.
PS. while i like the resolution ACCEPT/REJECT on the same line with the final state, it can me moved to solitude (e.g. imagine results are to be parsed by stupid script that only cares about last line being accept or reject) by adding '\n'+ (5 chars) to the last print for the price of +5 chars.
Example output:
# for empty input
S1 ACCEPT
# for input '1001010'
S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
S1 ACCEPT
# for input '101'
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 REJECT
# for input '10X'
S1 1 -> S1
S1 0 -> s2
s2 X REJECT
# for input 'X10'
S1 X REJECT