Python 2.7+, 201 192 187 181 179 175 171 chars

PS. Après que le problème a été assoupli (pas besoin d'indiquer la ligne de sortie sur l'entrée vide), voici un nouveau code qui est beaucoup plus court. Si vous êtes sur la version < 2.7, il n'y a pas de dict compréhension , donc au lieu de {c+o:s for o,c,s in i[1:-1]} essayer dict((c+o,s)for o,c,s in i[1:-1]) pour le prix de +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]

et sa sortie d'essai:

# 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

rubrique précédente (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]

je veux m'excuser avant que quelqu'un me tape dessus pour ça: le comportement du code est légèrement différent de la discussion initiale spec - per question-comments. C'est mon illustration pour la discussion.

PS. alors que j'aime la résolution accepter / rejeter sur la même ligne avec l'état final, il me peut passer à la solitude (par exemple, imaginez des résultats sont à interpréter par stupide script qui se soucie seulement de la dernière ligne accepter ou rejeter) en ajoutant '\n'+ (5 caractères) à la dernière print pour le prix de +5 caractères.

exemple de sortie:

# 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

je me sens rétro aujourd'hui, ma langue de choix pour cette tâche est IBM Enterprise Cobol-char count 2462 4078 (Désolé, collé d'un dispositif orienté écran, espaces traînants sont un effet secondaire tragique):

 Identification Division.               
 Program-ID. FSM.                       
 Environment Division.                  
 Data Division.                         
 Working-Storage Section.               

 01 FSM-Storage.                        

*> The current state                    
   05 Start-State      Pic X(2).        
   05 Next-State       Pic X(2).        

*> List of valid states                 
   05 FSM-State-Cnt    Pic 9.           
   05 FSM-States       Occurs 9         
                       Pic X(2).        

*> List of valid transitions            
   05 FSM-Trans-Cnt    Pic 999.         
   05 FSM-Trans        Occurs 999.      
     10 Trans-Start    Pic X(2).        
     10 Trans-Char     Pic X.           
     10 Trans-End      Pic X(2).        

*> Input                                
   05 In-Buff          Pic X(72).      

*> Some work fields                     
   05 II               Pic s9(8) binary.
   05 JJ               Pic s9(8) binary.

   05 Wk-Start         Pic X(2).        
   05 Wk-Char          Pic X.           
   05 Wk-End           Pic X(2).        
   05 Wk-Cnt           Pic 999.         

   05                  Pic X value ' '. 
     88 Valid-Input        value 'V'.   

   05                  Pic X value ' '.                 
     88 Valid-State        value 'V'.                   

   05                  Pic X value ' '.                 
     88 End-Of-States      value 'E'.                   

   05                  Pic X value ' '.                 
     88 Trans-Not-Found    value ' '.                   
     88 Trans-Found        value 'T'.                   


 Linkage Section.                                       

 01 The-Char-Area.                                      
   05 The-Char         Pic X.                           
     88 End-Of-Input       value x'13'.                 
   05 The-Next-Char    Pic X.                           

 Procedure Division.                                    

      Perform Load-States                               
      Perform Load-Transitions                          
      Perform Load-Input                                
      Perform Process-Input                             

      Goback.                                           

*> Run the machine...                                   
 Process-Input.                                         

      Move FSM-States (1) to Start-State                
      Set address of The-Char-Area to address of In-Buff

      Perform until End-Of-Input                        

        Perform Get-Next-State                          
        Set address of The-Char-Area to address of The-Next-Char

        Move Next-State to Start-State                          

      End-Perform                                               

      If Start-State (1:1) is Alphabetic-Lower                  
        Display 'REJECT'                                        
      Else                                                      
        Display 'ACCEPT'                                        
      End-If                                                    

      Exit.                                                     

*> Look up the first valid transition...                        
 Get-Next-State.                                                

      Set Trans-Not-Found to true                               
      Perform varying II from 1 by 1                            
        until (II > FSM-State-Cnt)                              
           or Trans-Found                                       

        If Start-State = Trans-Start (II)                       
          and The-Char = Trans-Char (II)                        

          Move Trans-End (II) to Next-State                     
          Set Trans-Found to true                               

        End-If                                                  

      End-Perform                                               
      Display Start-State ' ' The-Char ' -> ' Next-State        

      Exit.                                                     

*> Read the states in...                                        
 Load-States.                                                   

      Move low-values to In-Buff                         
      Accept In-Buff from SYSIN                          

      Move 0 to FSM-State-Cnt                            
      Unstring In-Buff                                   
        delimited by ' '                                 
        into FSM-States (1) FSM-States (2) FSM-States (3)
             FSM-States (4) FSM-States (5) FSM-States (6)
             FSM-States (7) FSM-States (8) FSM-States (9)
        count in FSM-State-Cnt                           
      End-Unstring                                       

      Exit.                                              

*> Read the transitions in...                            
 Load-Transitions.                                       

      Move low-values to In-Buff                         
      Accept In-Buff from SYSIN                          

      Perform varying II from 1 by 1                     
        until End-Of-States                              

        Move 0 to Wk-Cnt                                 
        Unstring In-Buff                                 
          delimited by ' '                               
          into Wk-Start Wk-Char Wk-End                   
          count in Wk-Cnt                                
        End-Unstring                                     

        If Wk-Cnt = 3                                    

          Add 1 to FSM-Trans-Cnt                         
          Move Wk-Start to Trans-Start (FSM-Trans-Cnt)   
          Move Wk-Char  to Trans-Char  (FSM-Trans-Cnt)   
          Move Wk-End   to Trans-End   (FSM-Trans-Cnt)   

          Move low-values to In-Buff                     
          Accept In-Buff from SYSIN                           

        Else                                                  

          Set End-Of-States to true                           

        End-If                                                

      End-Perform                                             

      Exit.                                                   

*> Fix input so it has newlines...the joys of mainframes      
 Load-Input.                                                  

      Perform varying II from length of In-Buff by -1         
        until Valid-Input                                     

        If In-Buff (II:1) = ' ' or In-Buff (II:1) = low-values
          Move x'13' to In-Buff (II:1)                        
        Else                                                  
          Set Valid-Input to true                             
        End-If                                                

      End-Perform                                             

      Exit.                                                   

  End Program FSM.    

sed -- 118 137 characters

ceci utilise le drapeau-r (+3), pour un total de 134+3=137 caractères.

$!{H;D}
/:/!{G;s/(\S*)..(\S*)/ :/}
s/(.* .)(.*\n (\S*))/ -> \n /
/-/{P;D}
/^[A-Z].* :/cACCEPT
s/( .).*//
/:/!P
cREJECT

cela devrait traiter correctement les entrées sans transition... espérons qu'il se conforme entièrement à la spécification maintenant...

Adam a fourni une mise en œuvre de référence. Je ne l'ai pas vu avant de faire le mien, mais la logique est similaire:

Edit: c'est le code python 2.6. Je n'ai pas essayer de minimiser la longueur; j'ai juste essayé de rendre conceptuellement simple.

import sys
a = sys.stdin.read().split('\n')
states = a[0].split()
transitions = a[1:-2]
input = a[-2]
statelist = {}
for state in states:
    statelist[state] = {}

for start, char, end in [x.split() for x in transitions]:
    statelist[start][char] = end

state = states[0]
for char in input:
    if char not in statelist[state]:
        print state,char
        print "REJECT"
        exit()
    newstate = statelist[state][char]
    print state, char, '->', newstate
    state = newstate
if state[0].upper() == state[0]:
    print "ACCEPT"
else:
    print "REJECT"

Python, 218 caractères

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()]

Haskell - 252 216 204 197 192 les caractères

s%(c:d,t)=s++' ':c:maybe('\n':x)(\[u]->" -> "++u++'\n':u%(d,t))(lookup[s,[c]]t)
s%_|s<"["="ACCEPT\n"|1<3=x
x="REJECT\n"
p(i:j)=(words i!!0)%(last j,map(splitAt 2.words)j)
main=interact$p.lines

est conforme aux spécifications de sortie.

version Ungolf'd:

type State = String
type Transition = ((State, Char), State)

run :: [Transition] -> State -> String -> [String]
run ts s (c:cs) =  maybe notFound found $ lookup (s,c) ts
  where
    notFound =  stateText                 : ["REJECT"]
    found u  = (stateText ++ " -> " ++ u) : run ts u cs
    stateText = s ++ " " ++ [c]

run _ (s:_) "" | s >= 'A' && s <= 'Z' = ["ACCEPT"]
               | otherwise            = ["REJECT"]

prepAndRun :: [String] -> [String]
prepAndRun (l0:ls) = run ts s0 input
  where
    s0 = head $ words l0
    input = last ls
    ts = map (makeEntry . words) $ init ls
    makeEntry [s,(c:_),t] = ((s,c),t)

main' = interact $ unlines . prepAndRun . lines

un bon puzzle est pourquoi init n'est pas nécessaire dans la version golf! En dehors de cela, le repos sont toutes les techniques de golf Haskell standard.

Perl-184 caractères

(Compter à l'exclusion de toutes les nouvelles lignes, qui sont facultatives.)

($s)=split' ',<>;$\=$/;
while(<>){chomp;$r{$_[1].$_[0]}=$_[2]if split>2;$t=$_}
$_=$t;
1 while$s&&s/(.)(.*)/print"$s ",($s=$r{.$s})?" -> $s":"";/e;
print$s=~/^[A-Z]/?"ACCEPT":"REJECT"

de plus, ce programme de 155 caractères n'implémente pas les sorties intermédiaires, mais exécute la machine entièrement comme une substitution répétée sur l'ensemble de la définition FSM (en changeant l'état de départ et la chaîne d'entrée). Elle s'inspire de la solution sed , mais n'en découle pas. Il pourrait être raccourci de 2 caractères en convertissant le (?:...) en un (...) et en renumérotant au besoin.

$/="";$_=<>;
1 while s/\A(\S+)(?: +\S+)*\n(.*\n)? +(.) +(.+)\n(.*\n)?([^\n]*)\n\z/\n  \n\n/s;
print/\A[A-Z].*\n\n\z/s?"ACCEPT\n":"REJECT\n"

Python 3, Chars: 203

Le format de sortie semble un peu difficile à intégrer.

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<'_'])

MIXAL 898 caractères

    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

Déify Knuth!

Haskell-189 caractères

main=interact$r.lines
r f=g t z$last f where{(z:_):t=map words f;g _ s""|s<"["="ACCEPT\n";g([q,j,p]:_)s(i:k)|i:s==j++q=s++' ':i:" -> "++p++'\n':g t p k;g(_:y)s i=g y s i;g _ _ _="REJECT\n"}

EDIT: n'implémente pas correctement la sortie pour le rejet de no-transition.

-- r: run FSM
-- f: fsm definition as lines
-- z: initial state

-- g: loop function
-- t: transition table
-- s: current state
-- i: current input
-- k: rest of input

-- q: transition table match state
-- j: transition table match input
-- p: transition table next state
-- y: tail of transition table

main=interact$r.lines;
r f=g t z$last f where{
(z:_):t=map words f;
g _ s""|s<"["="ACCEPT\n";
g([q,j,p]:_)s(i:k)|i:s==j++q=s++' ':i:" -> "++p++'\n':g t p k;
g(_:y)s i=g y s i;
g _ _ _="REJECT\n"}

j'ai obtenu la technique s<"[" de la solution de MtnViewMark; le reste est mon propre design. Caractéristiques notables:

• l'entrée est laissée comme junk dans la table de transition. C'est OK aussi longtemps que le l'entrée ne contient pas deux espaces, mais notez que le format de la règle de transition est de toute façon peu propice à la transition sur le caractère d'espace.
• passer à travers la chaîne de caractères et rechercher la table de transition sont la même fonction.
• les deux cas de rejet sont traités par la même erreur.

Common Lisp-725

(defun split (string)
  (loop for i = 0 then (1+ j)
     as j = (position #\Space string :start i)
     collect (subseq string i j)
     while j))

(defun do-fsm ()
  (let* ((lines (loop for l = (read-line *standard-input* nil)
      until (not l)
     collect (split l)))
  (cur (caar lines))
  (transitions (subseq lines 1 (- (length lines) 1))))
    (if (or (loop for c across (caar (last lines))
      do (format t "~a ~a" cur c)
        when (not (loop for tr in transitions
       when (and (equal cur (car tr))
          (equal c (char (cadr tr) 0)))
       return (progn (format t " -> ~a~%"
        (setq cur (caddr tr)))
       t)
         ))
        return t)
     (lower-case-p (char cur 0)))
 (format t "~%REJECT~%")
 (format t "ACCEPT~%"))))

pas de réelle tentative de minimiser le code -- Common Lisp paie une lourde pénalité dans le traitement requis des entrées, donc je ne pense pas qu'il y a beaucoup de chance que cette solution gagne : -)

Ruby-183

h={}
r=$<.read
t=s=r.split[0]
i=r[-1]=="
"?"":r.split[-1]
r.scan(/(\S+) (.) (.+)/){|a,b,c|h[[a,b]]=c}
i.chars{|c|puts s+" #{c} -> #{s=h[[s,c]]}"}
puts s&&s[/^[A-Z]/]?"ACCEPT":"REJECT"

vraiment, étrange spécification de sortie. Voici comment je travaille: http://ideone.com/cxweL

Rexx 205 caractères

(cette réponse a subi peu de modifications car je viens tout d'abord d'afficher un code d'intérêt général, puis j'ai décidé de poster une VRAIE solution)

Voici une version de Rexx pour donner aux gens un goût pour cette langue moins connue. Rexx http://en.wikipedia.org/wiki/REXX est un langage interprété utilisé dans le VM/CMS mainframe operating system D'IBM et plus tard dans IBM OS / 2 (et je crois qu'il y avait une variante de L'Amiga). C'est un langage expressif et d'une étonnante usage général/"script" de la langue.

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)

cela peut être exécuté avec l'interpréteur Regina Rexx .

gérer le scénario de transition incorrect avec sa sortie unique et aussi des tests pour majuscules est un peu cher.

Code de quelques versions plus anciennes ci-dessous pour les personnes intéressées par la syntaxe Rexx, celles-ci ne sont pas 100% conformes avec les exigences de sortie mais sont fonctionnelles (tout le code dans cette réponse fonctionne avec les échantillons que j'ai collés ci-dessous, mais le code ci-dessus gère les autres coins requis):

version courte plus ancienne:

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'

version plus longue:

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'

entrée/sortie de L'échantillon:

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

Lua, 356

prend tous les caractères non-espace pour les États, et tous les caractères non-espace un pour les lettres de transition. Bien que cela ne semble pas le plus court, je le posterai de n'importe quelle façon. Pourrait sauver 25 caractères d'impression tabs au lieu d'espaces.

version lisible:

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)

version Golfée + Sortie in - an.

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

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

notez que cela nécessite en fait bash-POSIX sh n'a pas de tableaux associatifs ou le style C pour la syntaxe (et n'a probablement pas toutes les extensions de paramètre utilisées, bien que je n'ai pas vérifié).

modifier: alternativement, pour la même longueur exacte,

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

Python (2.6) ~ 269 characters.

probablement encore de la place pour l'amélioration, conseils bienvenus. Poignées de spécifications, je pense.

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]]

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')

vérifier la version en cours d'exécution sur codepad ancienne version

F# 420

pas mal pour un golf immuable. Je n'ai pas très bien sur le parcours aujourd'hui.

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 lignes de l'onu-ont joué au golf F#. Je vous tiendrai au courant après mon golfage.

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"

C# - 453 375 353 345 les caractères

cela ne gagne pas (personne n'aurait dû s'y attendre), mais c'était quand même amusant d'écrire. J'ai gardé les espaces de tête et les nouvelles lignes pour la lisibilité:

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"));
  }
}

dans ma dernière mise à jour j'ai pu sauvegarder 22 caractères en supposant une limite pratique au nombre de lignes d'entrée (à savoir 99 999). Dans le pire des cas, vous aurez besoin de monter cela à la Int32 max de 2.147.483.647 qui ajouterait 5 chars. Ma machine n'aime pas l'idée d'un tableau qui, bien qu'...

exemple d'exécution:

>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