Ответ 1

Ruby 1.9.2 - 178 190 182 177 153 161 158 154 145 символов

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

Тестирование 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

Выходы

Все входные данные начинаются с:

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

Ответ 2

Python 2.7+, 201 192 187 181 179 175 171 символ

PS. После устранения проблемы (нет необходимости выводить строку состояния на пустой вход), вот новый код, который заметно короче. Если вы находитесь на версии 2.7, то нет понимания dict, поэтому вместо {c+o:s for o,c,s in i[1:-1]} попробуйте dict((c+o,s)for o,c,s in i[1:-1]) по цене +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]

И его тестовый результат:

# 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

Предыдущая запись (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]

Я хочу извиниться перед тем, как кто-то похлопывает меня за это: поведение кода немного отличается от первоначального обсуждения вопросов-комментариев. Это моя иллюстрация для обсуждения.

PS. в то время как мне нравится разрешение ACCEPT/REJECT в той же строке с конечным состоянием, оно может меня переместиться в уединение (например, представьте, что результаты должны анализироваться глупым script, который заботится только о том, что последняя строка принимает или отклоняет) путем добавления '\n'+ (5 символов) до последнего print по цене +5 символов.

Пример вывода:

# 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

Ответ 3

Я чувствую ретро сегодня, мой язык выбора для этой задачи - IBM Enterprise Cobol - char count 2462 4078 (Извините, вставляемый с экрана ориентированного устройства, конечные пробелы трагичны побочный эффект):

 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.    

Ответ 4

sed - 118 137 символов

Используется флаг -r (+3), в общей сложности 134 + 3 = 137 символов.

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

Это должно обрабатывать входы без переходов правильно... надеюсь, что он полностью соответствует спецификации теперь...

Ответ 5

Адам предоставил справочную реализацию. Я не видел этого, прежде чем я сделал свой, но логика схожа:

Изменить: Это код Python 2.6. Я не пытался минимизировать длину; Я просто попытался сделать его концептуально простым.

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"

Ответ 6

Python, 218 символов

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

Ответ 7

Haskell - 252 216 204 197 192 символа

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

Соответствует спецификации вывода.

Версия 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

Хорошая головоломка - вот почему init не нужен в версии для гольфа! Помимо этого, отдых - это все стандартные технологии гольфа Haskell.

Ответ 8

Perl - 184 символа

(Count, исключая все новые строки, которые являются необязательными.)

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

Кроме того, эта 155-символьная программа не реализует промежуточные выходы, но выполняет машину полностью как повторную подстановку во всем определении FSM (изменение начального состояния и вводной строки). Он был вдохновлен, но не получен из решения sed. Его можно сократить на 2 символа, преобразов (?:...) в (...) и перенумеровав при необходимости.

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

Ответ 9

Python 3, Chars: 203

Формат вывода кажется немного сложным.

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

Ответ 10

MIXAL 898 символов

    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!

Ответ 11

Haskell - 189 символов

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: неправильно реализует вывод для отказа от отказа.

Линейная версия и руководство по переменной:

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

Я получил метод s<"[" из решения MtnViewMark; остальное - мой собственный дизайн. Известные характеристики:

• В таблице переходов вход сохраняется как нежелательный. Это нормально, пока вход не содержит двух пробелов; но обратите внимание, что формат правила перехода, возможно, недружелюбен для перехода на символ пробела.
• Выполнение входной строки и поиск таблицы переходов - одна и та же функция.
• Оба случая REJECT обрабатываются одним и тем же провалом.

Ответ 12

Общий 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~%"))))

Нет реальной попытки свести к минимуму код. Обычный Lisp платит тяжелый штраф за требуемую обработку ввода, поэтому я не думаю, что у этого шанса есть много шансов:-)

Ответ 13

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"

Действительно, странная спецификация выхода. Вот как мои работы: http://ideone.com/cxweL

Ответ 14

Rexx 205 символов

(Этот ответ прошел несколько изменений, поскольку я изначально просто разместил код для общего интереса, а затем решил фактически опубликовать реальное решение)

Здесь версия Rexx, чтобы дать людям вкус к этому менее известному lanugage. Rexx http://en.wikipedia.org/wiki/REXX - это интерпретируемый язык, используемый в операционной системе IBM VM/CMS, а затем в IBM OS/2 (и я считаю, что Амига). Это очень выразительный язык и потрясающий общий/ "скриптовый" язык.

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)

Это можно запустить с помощью интерпретатора Regina Rexx.

Обработка неправильного сценария перехода с его уникальным результатом, а также тестирование для прописных букв немного дороже.

Код из некоторых старых редакций ниже для людей, заинтересованных в синтаксисе Rexx, они не соответствуют требованиям выходных требований на 100%, но являются функциональными (весь код в этом ответе работает с образцами, вставленными ниже, но код выше обрабатывает другие требуемые углы):

Старая короткая версия:

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'

Более длинная версия:

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

Пример ввода/вывода:

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

Ответ 15

Lua, 356

Принимает любые нестерические символы для состояний и любые непространственные символы для символов перехода. Хотя это кажется не самым коротким, я отправлю его любым способом. Не удалось сохранить 25 строк печати вместо пробелов.

Считываемая версия:

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)

версия для гольфа + выход.

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

Ответ 16

bash - 186 185 184 символа

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

Обратите внимание, что это на самом деле требуется bash - POSIX ш не имеет ассоциативные массивы или C-стиль синтаксиса (и, вероятно, не все расширения параметров, используемых либо, хотя я не проверял).

Изменить: альтернативно, для той же длины,

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

Ответ 17

Python (2.6) ~ 269 символов.

Вероятно, еще место для улучшения, приветствия приветствуются. Характеристики ручек, я думаю.

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

Ответ 18

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

проверить запущенную версию на codepad старая версияудаp >

Ответ 19

С# - 453 375 353 345 символов

Это не побеждает (не то, чтобы кто-то ожидал этого), но все равно было интересно писать. Я сохранил ведущие пробелы и новые строки для удобочитаемости:

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

В моем последнем обновлении мне удалось сохранить 22 символа, предположив практическое ограничение количества входных строк (а именно 99,999). В худшем случае вам нужно довести до Int32 max 2,147,483,647, что добавит 5 символов. Моя машина не любит идею массива, которая долгое время...

Пример выполнения:

>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

Ответ 20

F # 420

Неплохо для неизменного гольфа, я думаю. Сегодня я не очень хорошо поработал на этом курсе.

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 линии для не-гольф F #. Я немного обновлюсь после игры в гольф.

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"