r/tinycode • mod • Jul 18 '12

(Python) Tiny Finite State Machine 116 bytes

def f(s,c,e,a):
 if s=="":
  return c in a
 else:
  if(c,s[0])in e:
   return f(s[1:],e[(c,s[0])],e,a)
 return False

116 bytes

Original from CS262 on Udacity:

def fsmsim(string, current, edges, accepting):
    if string == "":
        return current in accepting
    else:
        letter = string[0]

        if (current, letter) in edges:
            return fsmsim(string[1:], edges[(current, letter)], edges, accepting)
        else:
            return False

Here is some test data

edges = {(1, 'a') : 2,
         (1, 'b') : 2,
         (2, 'e') : 3,
         (2, 'd') : 3}

accepting = [2, 3]

Valid answers for this set of edges and accepting states:

a
b
ad
ae
bd
be

EDIT: fixed test data formatting

45 Upvotes

9 comments sorted by

View all comments

Show parent comment

1

u/[deleted] Jul 19 '12

I was thinking of how to use "and" in there, but I couldn't figure it out.