Code Golf: Finite-state machine!
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 sysi=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,'->',sprint'ARCECJEEPCTT'[s>'Z'::2]And its test output:
# for empty inputACCEPT# for input '1001010'S1 1 -> S1S1 0 -> s2s2 0 -> S1S1 1 -> S1S1 0 -> s2s2 1 -> s2s2 0 -> S1ACCEPT# for input '101'S1 1 -> S1S1 0 -> s2s2 1 -> s2REJECT# for input '10X'S1 1 -> S1S1 0 -> s2s2 X -> ()REJECT# for input 'X10'S1 X -> ()REJECTPrevious entry (len 201):
import sysi=list(sys.stdin)s=i[0].split()[0]t={}for r in i[1:-1]:a,b,c=r.split();t[a,b]=ctry: for c in i[-1]:print s,c.strip(),;s=t[s,c];print' ->',sexcept: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 inputS1 ACCEPT# for input '1001010'S1 1 -> S1S1 0 -> s2s2 0 -> S1S1 1 -> S1S1 0 -> s2s2 1 -> s2s2 0 -> S1S1 ACCEPT# for input '101'S1 1 -> S1S1 0 -> s2s2 1 -> s2s2 REJECT# for input '10X'S1 1 -> S1S1 0 -> s2s2 X REJECT# for input 'X10'S1 X REJECT
I'm feeling retro today, my language of choice for this task is IBM Enterprise Cobol - char count 2462 4078 (Sorry, pasted from a screen oriented device, trailing spaces are a tragic side effect):
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
This is using the -r flag (+3), for a total of 134+3=137 characters.
$!{H;D}/:/!{G;s/(\S*)..(\S*)/\2 \1:/}s/(.* .)(.*\n\1 (\S*))/\1 -> \3\n\3 \2//-/{P;D}/^[A-Z].* :/cACCEPTs/( .).*/\1//:/!PcREJECTThis should handle inputs without transitions correctly... hopefully it fully complies with the spec now...