Code Golf: Finite-state machine!

Question

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:

1. alphabet, a set of characters.
2. 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.
3. transitions, usually visualized as directed arches between states, are directed links between states associated with an alphabet letter.
4. 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:

1. The alphabet is the set {0,1}.
2. The states are S1 and S2.
3. The transitions are (S1, 0) -> S2, (S1, 1) -> S1, (S2, 0) -> S1 and (S2, 1) -> S2.
4. 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 1

Python, 218 characters

import sys
T=sys.stdin.read()
P=T.split()
S=P[0]
n="\n"
for L in P[-1]if T[-2]!=n else"":
 i=T.find(n+S+" "+L)
 if i<0:print S,L;S=n;break
 S=T[i:].split()[2];print S,L,"->",S
print ("REJECT","ACCEPT")[S[0].isupper()]

Answer 2

Lua - 248 227

r=...
p=print
M={}
s=r:match('(%a%d)')
for i,n,o in r:gmatch('(%a%d)%s(%d)%s(%a%d)')do
M[i]=M[i]or{}
M[i][n]=o
end
for c in r:match('%d%d+'):gmatch('(%d)')do
z=s
s=M[z][c]
p(z,c,'->',s)
end
p(s==s:upper()and'ACCEPT'or'REJECT')

check running version on codepad old version

Answer 3

bash - 186 185 184 chars

declare -A a
read s x
while read f m t&&[ $m ];do a[$f $m]=$t;done
for((i=0;i-${#f};i++))do b="$s ${f:i:1}";s=${a[$b]};echo $b -\> $s;done
[ "$s" = "${s,}" ]&&echo REJECT||echo ACCEPT

Note that this does actually require bash - POSIX sh doesn't have associative arrays or the C-style for syntax (and probably doesn't have all the parameter expansions used either, although I haven't checked).

Edit: alternatively, for the exact same length,

declare -A a
read s x
while read f m t&&[ $m ];do a[$f $m]=$t;done
while [ $f ];do b="$s ${f:i:1}";f=${f:1};s=${a[$b]};echo $b -\> $s;done
[ "$s" = "${s,}" ]&&echo REJECT||echo ACCEPT

Answer 4

Ruby 1.9.2 - 178 190 182 177 153 161 158 154 145 characters

h={}
o=s=p
$<.map{|l|o,b,c=l.split;h[[o,b]]=c;s||=o}
o.chars{|c|puts s+' '+c+((s=h[[s,c]])?' -> '+s :'')}rescue 0
puts s&&s<'['?:ACCEPT: :REJECT

Testing Script

[
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
1001010",
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
101",
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
",
  "S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
10X"
].each do |b|
  puts "------"
  puts "Input:"
  puts b
  puts
  puts "Output:"
  puts `echo "#{b}" | ruby fsm-golf.rb`
  puts "------"
end

Outputs

All input starts with:

S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2

---

Input: '1001010'
Output:
S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
ACCEPT

Input: '101'
Output:
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
REJECT

Input: 'X10'
Output:
S1 X
REJECT

Input: ''
Output:
ACCEPT

Input: '10X'
Output:
S1 1 -> S1
S1 0 -> s2
s2 X
REJECT

Answer 5

Rexx 205 characters

(This answer went through few edits as I initially just posted some code for general interest and then decided to actually post a real solution)

Here's a Rexx version to give people a taste for that less known lanugage. Rexx http://en.wikipedia.org/wiki/REXX is an interpreted language used in IBM's VM/CMS mainframe operating system and later in IBM OS/2 (and I believe there was an Amiga variant). It's a very expressive language and an amazing general purpose/"scripting" language.

Parse pull i .
d.='~'
Do until l='';Parse pull o l d.o.l;End
Do j=1 to LENGTH(o)
t=SUBSTR(o,j,1);p=i t;i=d.i.t
If i=d. then Do;Say p;Leave;End
Say p '->' i
End
Say WORD('ACCEPT REJECT',c2d(left(i,1))%32-1)

This can be run with the Regina Rexx interpreter.

Handling the incorrect transition scenario with its unique output and also testing for uppercase is a bit expensive.

Code from some older edits below for people interested in the Rexx syntax, those aren't 100% compliant with the output requirements but are functional (all code in this answer works with the samples I pasted below but the code above handles the other required corners):

Older short version:

Parse pull i .
Do until l = ""; Parse pull o l d; t.o.l = d; End
Do j=1 to LENGTH(o); t=substr(o,j,1); Say i t "->" t.i.t; i=t.i.t; End
If LEFT(i,1)='S' then Say 'ACCEPT'; else say 'REJECT'

Longer version:

Parse pull initial . /* Rexx has a powerful built in string parser, this takes the first word into initial */

Do until letter = "" /* This style of do loops is a bit unusual, note how it doesn't matter that letter isn't defined yet */
  Parse pull origin letter destination /* Here we parse the inpt line into three words */
  transition.origin.letter = destination /* Rexx has a very powerful notion of associative containers/dictionaries, many years pre-Python */
End

/* Now we take the last line and iterate over the transitions */
Do i = 1 to LENGTH(origin) 
  t = substr(origin, i, 1) /* This is the actual letter using Rexx's string functions */
  Say initial t "->" transition.initial.t /* Say is like print */
  initial = transition.initial.t /* Perform the transition */
End

/* check for uppercase in the current state */
if left(initial, 1) = 'S' then Say 'ACCEPT'; else say 'REJECT'

Sample in/out:

S1 s2
S1 0 s2
0
S1 0 -> s2
REJECT

S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
1001010
S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
ACCEPT

Answer 6

Python 3, Chars: 203

The output format seems a bit hard to fit.

import sys
L=[i.split()for i in sys.stdin]
N,P=L[0][0],print
for c in L[-1]and L[-1][-1]:
 if N:O,N=N,{(i[0],i[1]):i[2]for i in L[1:-1]}.get((N,c),'');P(O,c,N and'-> '+N)
P(('REJECT','ACCEPT')[''<N<'_'])