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 (2.6) ~ 269 characters.

Probably still room for improvement, hints welcome. Handles specifications I think.

import sys;a=sys.stdin.readlines();b=a[0].split()
f=b[0];d=dict((x,{})for x in b);s=''
for x,y,z in map(str.split,a[1:-1]):d[x][y]=z
for g in a[-1]:
 try:s+=f+' '+g;f=d[f][g];s+=' -> '+f+'\n'
 except:s+='\n';break
print s+("REJECT","ACCEPT")[ord(f[0])<90 and g in d[f]]

Answer 2

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

Answer 3

F# 420

Not bad for immutable golf I think. I didn't do very good on the course today though.

open System
let f,p,a=Array.fold,printf,Map.add
let l=Console.In.ReadToEnd().Split '\n'
let e,s=l.Length,l.[0].Split ' '
let t,w=Map.ofList[for q in s->q,Map.empty],[|"ACCEPT";"REJECT"|]
let m=f(fun t (r:String)->let s=r.Split ' 'in a s.[0](t.[s.[0]]|>a s.[1].[0]s.[2])t)t l.[1..e-2]
try let r=l.[e-1].ToCharArray()|>f(fun s c->p"%s %c "s c;let n=m.[s].[c]in p"-> %s\n"n;n)s.[0]in p"%s"w.[int r.[0]/97]with|_->p"%s"w.[1]

33 lines for un-golfed F#. I'll update again in a bit after I've golfed.

open System

let input = Console.In.ReadToEnd()
//let input = "S1 s2\nS1 0 s2\nS1 1 S1\ns2 0 S1\ns2 1 s2\n1001010"
let lines = input.Split '\n'
let length = lines.Length
let states = lines.[0].Split ' '

let stateMap = Map.ofList [for state in states -> (state, Map.empty)]

let folder stateMap (line:String) =
    let s = line.Split ' '
    stateMap |> Map.add s.[0] (stateMap.[s.[0]] |> Map.add s.[1].[0] s.[2])

let machine = Array.fold folder stateMap lines.[1 .. (length-2)]

let stateMachine state char =
    printf "%s %c " state char
    let newState = machine.[state].[char]
    printfn "-> %s" newState
    newState

try
    let result = 
        lines.[length-1].ToCharArray()
        |> Array.fold stateMachine states.[0]

    if Char.IsUpper result.[0] then
        printf "ACCEPT"
    else
        printf "REJECT"
with
    | _ -> printf "REJECT"

Answer 4

C# - 453 375 353 345 characters

This doesn't win (not that anyone should have expected it to), but it was fun to write anyway. I kept the leading spaces and newlines for legibility:

using System;
class P
{
  static void Main()
  {
    string c,k="";
    var t=new string[99999][];
    int p=-1,n;
    while((c=Console.ReadLine())!="")
      t[++p]=c.Split(' ');

    c=t[0][0];
    foreach(var d in t[p][0]){
      k+=c+' '+d;
      for(n=1;n<p;n++)
        if(c==t[n][0]&&d==t[n][1][0])
      {
        c=t[n][2];
        k+=" -> "+c;
        break;
      }
      k+="\n";
      if(n==p){
        c="~";
        break;
      }
    }
    Console.Write(k+(c[0]>'Z'?"REJECT":"ACCEPT"));
  }
}

In my last update I was able to save 22 characters by assuming a practical limit to the number of input rows (namely 99,999). In the worst case, you'd need to up that to the Int32 max of 2,147,483,647 which would add 5 chars. My machine doesn't like the idea of an array that long though...

An example of the execution:

>FSM.exe
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 5

MIXAL 898 characters

    ORIG    3910
A   ALF ACCEP
    ALF T    
    ORIG    3940
R   ALF REJEC
    ALF T    
    ORIG    3970
O   CON 0
    ALF ->   
    ORIG    3000
S   ENT6    0
T   IN  0,6(19)
    INC6    14
    JBUS    *(19)
    LDA -14,6
    JANZ    T
    LDA -28,6(9)
    DECA    30
    JAZ C
    DECA    1
    JANZ    B
C   LD2 0(10)
    ENT4    -28,6
    ENT5    9
D   JMP G
    ENT3    0
F   INC3    14
    LD1 0,3(10)
    DEC2    0,1
    J2Z M
    INC2    0,1
    DEC3    -28,6
    J3NN    U
    INC3    -28,6
    JMP F
M   INC2    0,1
    LD1 0,3(36)
    DECA    0,1
    JAZ H
    INCA    0,1
    JMP F
H   INCA    0,1
    ST2 O(10)
    LD2 1,3(10)
    STA O(36)
    ST2 O+1(37)
    OUT O(18)
    JBUS    *(18)
    JMP D
    HLT
E   LD1 0(10)
    DEC1    0,2
    J1Z B
U   OUT R(18)
    JBUS    *(18)
    HLT
B   OUT A(18)
    JBUS    *(18)
    HLT
G   STJ K
    ST5 *+1(36)
    LDA 0,4
    JAZ E
    DECA    30
    JAZ I
    DECA    1
    JANZ    W
    INCA    1
I   INCA    30
    DEC5    45
    J5NN    J
    INC5    54
    JMP K
J   INC4    1
    ENT5    9
K   JMP *
W   ST2 O(10)
    INCA    31
    STA O(36)
    STZ O+1
    OUT O(18)
    JBUS    *(18)
    JMP B
    END S

Deify Knuth!

Answer 6

Lua, 356

Takes any nonspace characters for states, and any non-space one characters for transition letters. Though it seems not shortest, I'll post it any way. Could save 25 chars printing tabs instead of spaces.

Readable version:

i=io.read
p=print
S={}
i():gsub("(%S+)",function (a) f=f or a S[a]={} end )
l=i"*a"
for a,t,d in l:gmatch"(%S+) (%S) (%S+)"do
    S[a][t]=d
end
I=l:match"(%S+)%s$"or"" -- fixes empty input
function F(a,i)
    t=I:sub(i,i)
    if t==""then
        p"ACCEPT"
    elseif S[a][t] then
        p(("%s %s -> %s"):format(a,t, S[a][t]))
        return F( S[a][t],i+1)
    else
        if t~=""then p(a.." "..t)end p'REJECT'
    end
end
F(f,1)

Golfed version + in- an output.

i=io.read p=print S={}i():gsub('(%S+)',function(a)f=f or a S[a]={}end)l=i'*a'for a,t,d in l:gmatch"(%S+) (%S) (%S+)"do S[a][t]=d end I=l:match'(%S+)%s$'or''function F(a,i)t=I:sub(i,i)if t==""and a:match'^%u'then p'ACCEPT'elseif S[a][t]then p(('%s %s -> %s'):format(a,t,S[a][t]))return F(S[a][t],i+1)else if t~=''then p(a.." "..t)end p'REJECT'end end F(f,1)
-- input --
A B C   
A B B
A C C
A A A
B A A 
B B B
B C C
C A A 
C B B
C C C
AABCCBCBAX
-- output --

A A -> A
A A -> A
A B -> B
B C -> C
C C -> C
C B -> B
B C -> C
C B -> B
B A -> A
REJECT