estados - graficar automatas en python

Code Golf: máquina de estado finito!

Question

Máquina de estados finitos

Una máquina determinista de estados finitos es un modelo de computación simple, ampliamente utilizado como introducción a la teoría de autómatas en cursos básicos de CS. Es un modelo simple, equivalente a la expresión regular, que determina si una determinada cadena de entrada es Aceptada o Rechazada . Dejando algunas formalidades a un lado , una ejecución de una máquina de estados finitos se compone de:

1. alfabeto , un conjunto de caracteres.
2. estados , generalmente visualizados como círculos. Uno de los estados debe ser el estado de inicio . Algunos de los estados podrían estar aceptando , generalmente visualizados como círculos dobles.
3. las transiciones , generalmente visualizadas como arcos dirigidos entre estados, son enlaces dirigidos entre estados asociados con una letra del alfabeto.
4. cadena de entrada , una lista de caracteres del alfabeto .

Una ejecución en la máquina comienza en el estado inicial. Cada letra de la cadena de entrada es leída; Si hay una transición entre el estado actual y otro estado que corresponde a la letra, el estado actual cambia al nuevo estado. Después de leer la última letra, si el estado actual es un estado de aceptación, se acepta la cadena de entrada. Si el último estado no fue aceptado, o si una letra no tenía un arco correspondiente desde un estado durante la ejecución, la cadena de entrada se rechaza.

Nota: Esta breve descripción está lejos de ser una definición formal completa de un FSM; El excelente artículo de Wikipedia es una excelente introducción al tema.

Ejemplo

Por ejemplo, la siguiente máquina indica si un número binario, leído de izquierda a derecha, tiene un número par de 0 s:

1. El alfabeto es el conjunto {0,1} .
2. Los estados son S1 y S2.
3. Las transiciones son (S1, 0) -> S2 , (S1, 1) -> S1 , (S2, 0) -> S1 y (S2, 1) -> S2 .
4. La cadena de entrada es cualquier número binario, incluida una cadena vacía.

Las normas:

Implemente un FSM en el idioma que elija.

Entrada

El FSM debe aceptar la siguiente entrada:

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

Por ejemplo, la máquina antes mencionada con 1001010 como una cadena de entrada, se escribiría como:

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

Salida

Ejecución del FSM, escrito como <State> <letter> -> <state> , seguido por el estado final. El resultado para la entrada de ejemplo sería:

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

Para la entrada vacía '''' :

S1
ACCEPT

Nota: Después de sus comentarios, la línea S1 (que muestra el primer estado) puede omitirse, y la siguiente salida también es aceptable:

ACCEPT

Para 101 :

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

Para ''10X'' :

S1 1 -> S1
S1 0 -> s2
s2 X
REJECT

Premio

Se otorgará una recompensa de 250 rep a la solución más corta.

Implementación de referencia

Una implementación de Python de referencia está disponible aquí . Tenga en cuenta que los requisitos de salida se han relajado para la entrada de cadenas vacías.

Apéndice

Formato de salida

Siguiendo la demanda popular, el siguiente resultado también es aceptable para la cadena de entrada vacía:

ACCEPT

o

REJECT

Sin el primer estado escrito en la línea anterior.

Nombres de estado

Los nombres de estado válidos son una letra inglesa seguida de cualquier número de letras, _ y dígitos, al igual que los nombres de las variables, por ejemplo, state0 , STATE_0 , STATE_0 .

Formato de entrada

Al igual que la mayoría de los campos de golf de código, puede asumir que su entrada es correcta.

Resumen de respuestas:

• Cobol - 4078 caracteres
• Python: 171 caracteres , 568 caracteres , 203 caracteres , 218 caracteres , 269 ​​caracteres
• sed - 137 letras
• ruby - 145 caracteres , 183 caracteres
• Haskell - 192 caracteres , 189 caracteres
• LISP - 725 caracteres
• Perl - 184 personajes
• Bash - 184 personajes
• Rexx - 205 caracteres
• Lua - 356 personajes
• F # - 420 caracteres
• C # - 356 caracteres
• Mixal - 898 caracteres

La solución de sed 137 es la más corta, el rubí 145 es el n.º 2. Actualmente, no puedo lograr que la solución sed funcione:

cat test.fsm | sed -r solution.sed
sed -r solution.sed test.fsm

ambos me dieron:

sed: -e expression #1, char 12: unterminated `s'' command

así que a menos que haya aclaraciones, la recompensa va a la solución de rubí.

Answer 1

Python (2.6) ~ 269 caracteres.

Probablemente todavía hay margen de mejora, sugerencias bienvenidas. Maneja las especificaciones, creo.

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, 218 caracteres

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 3

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"

Realmente, especificación de salida extraña. Aquí cómo funciona mi trabajo: http://ideone.com/cxweL

Answer 4

Adam proporcionó una implementación de referencia. No lo vi antes de hacer el mío, pero la lógica es similar:

Editar: este es el código de Python 2.6. No intenté minimizar la longitud; Solo traté de hacerlo conceptualmente 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"

Answer 5

Haskell - 252 216 204 197 192 caracteres

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

Cumple con la especificación de salida.

Versión sin ligar:

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 buen acertijo es por qué no se necesita init en la versión de golf! Aparte de eso, el resto son todas las técnicas de golf Haskell estándar.

Answer 6

Rexx 205 letras

(Esta respuesta recibió algunas modificaciones ya que inicialmente solo publiqué un código de interés general y luego decidí publicar una solución real)

Aquí hay una versión Rexx para darle gusto a la gente por ese estilo menos conocido. Rexx http://en.wikipedia.org/wiki/REXX es un lenguaje interpretado utilizado en el sistema operativo de mainframe VM / CMS de IBM y más tarde en IBM OS / 2 (y creo que hubo una variante de Amiga). Es un lenguaje muy expresivo y un sorprendente lenguaje de propósito general / "scripting".

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)

Esto se puede ejecutar con el intérprete Regina Rexx .

Manejar el escenario de transición incorrecto con su salida única y también probar en mayúsculas es un poco caro.

Código de algunas ediciones anteriores para personas interesadas en la sintaxis Rexx, no son 100% compatibles con los requisitos de salida pero son funcionales (todo el código de esta respuesta funciona con las muestras que pegué a continuación, pero el código anterior maneja las otras esquinas necesarias )

Versión corta anterior:

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

Versión más larga:

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

Muestra de entrada / salida:

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 7

Haskell - 189 personajes

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

EDITAR: no implementa correctamente la salida para el rechazo sin transición.

Versión de línea rota y guía variable:

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

Obtuve la técnica s<"[" de la solución de MtnViewMark; el resto es mi propio diseño Características notables:

• La entrada se deja como basura en la tabla de transición. Esto está bien siempre que la entrada no contenga dos espacios; pero tenga en cuenta que el formato de la regla de transición es posiblemente poco amistoso a la transición en el carácter del espacio de todos modos.
• Recorrer la cadena de entrada y buscar en la tabla de transición son la misma función.
• Ambos casos de RECHAZO son manejados por el mismo avance.

Answer 8

Perl - 184 personajes

(El recuento excluye todas las nuevas líneas, que son opcionales).

($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"

Además, este programa de 155 caracteres no implementa las salidas intermedias, sino que ejecuta la máquina completamente como una sustitución repetida en toda la definición de FSM (cambiando el estado de inicio y la cadena de entrada). Fue inspirado por, pero no derivado de, la solución sed . Podría acortarse en 2 caracteres convirtiendo el (?:...) en un (...) y renumerando según sea necesario.

$/="";$_=<>;
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"

Answer 9

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

comprobar la versión en ejecución en la versión anterior del teclado

Answer 10

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~%"))))

No hay un intento real de minimizar el código - Common Lisp paga una fuerte penalización en el procesamiento de entrada requerido, así que no creo que haya muchas posibilidades de que gane esta solución :-)

Answer 11

Python 3, Caracteres: 203

El formato de salida parece un poco difícil de ajustar.

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

Answer 12

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

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

Salidas

Toda la entrada comienza con:

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 13

sed - 118 137 caracteres

Esto está usando el indicador -r (+3), para un total de 134 + 3 = 137 caracteres.

$!{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

Esto debería manejar las entradas sin transiciones correctamente ... espero que cumpla totalmente con la especificación ahora ...

Answer 14

Me siento retro hoy, mi lenguaje de elección para esta tarea es IBM Enterprise Cobol - char count 2462 4078 (Lo siento, pegado desde un dispositivo orientado a la pantalla, los espacios al final son un efecto secundario trágico):

 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. 

Answer 15

F # 420

No está mal para el golf inmutable, creo. Aunque no hice muy bien el curso hoy.

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 líneas para F # sin golf. Actualizaré de nuevo un poco después de haber jugado al golf.

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 16

bash - 186 185 184 caracteres

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

Tenga en cuenta que esto realmente requiere bash: POSIX sh no tiene matrices asociativas o el estilo C para la sintaxis (y probablemente tampoco tenga todas las expansiones de parámetros utilizadas, aunque no lo he comprobado).

Editar: alternativamente, para la misma longitud exacta,

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 17

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

PD. Después de que el problema se relajó (no es necesario generar una línea de estado en la entrada vacía), aquí hay un código nuevo que es notablemente más corto. Si está en la versión <2.7, no hay comprensión del dictado , entonces en lugar de {c+o:s for o,c,s in i[1:-1]} pruebe dict((c+o,s)for o,c,s in i[1:-1]) por el precio 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]

Y su resultado de prueba:

# 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

Entrada anterior (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]

Quiero disculparme antes de que alguien me dé una bofetada: el comportamiento del código es ligeramente diferente al de la especificación original, por discusión de preguntas y comentarios. Esta es mi ilustración para la discusión.

PD. aunque me gusta la resolución ACEPTAR / RECHAZAR en la misma línea que el estado final, puedo moverme a la soledad (por ejemplo, imagine que los resultados deben ser analizados por un estúpido script que solo se preocupa de aceptar o rechazar la última línea) al agregar ''/n''+ (5 caracteres) a la última print por el precio de +5 caracteres.

Ejemplo de salida:

# 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 18

C # - 453 375 353 345 caracteres

Esto no gana (no es que nadie debería haber esperado que), pero fue muy divertido de escribir de todos modos. Seguí los espacios iniciales y saltos de línea para la legibilidad:

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

En mi última actualización pude salvar a 22 caracteres asumiendo un límite práctico al número de filas de entrada (es decir, 99.999). En el peor de los casos, que había necesidad de que hasta la Int32 máximo de 2147483647 que se sumaría 5 caracteres. Mi máquina no le gusta la idea de una matriz que mucho tiempo sin embargo ...

Un ejemplo de la ejecución:

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

Lua, 356

Toma cualquier carácter no espacial para estados y cualquier carácter no espacial para letras de transición. Aunque parece no ser el más corto, lo publicaré de cualquier manera. Podría guardar 25 pestañas de impresión de caracteres en lugar de espacios.

Versión legible:

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)

Versión Golfed + en una salida.

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

Answer 20

MIXAL 898 caracteres

 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!