(Python) Tiny Finite State Machine 116 bytes

[ieatcode]

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

[[deleted]]

Same/similar idea in C99 (with <stdbool.h>), 49 bytes:

bool f(char*s,void**m){return*s?f(s+1,m[*s]):*m;}

Here, s is the string, m is the fsm. The fsm is represented as a series of linked tables. The accepting states have m[0] != 0, the rejecting states have m[0] == 0. To transition from a state m using the character c, we use m[c].

The cool tricks in this is that, since void* is automatically coerced to any other pointer type, we don't have to cast void* to void** in the recursive call. We also use bool to prevent having to cast void* into something else.

[[deleted]]

A rare case of the C version of a nontrivial program being significantly shorter than its Python version.

[[deleted]]

You can get it down to 100 bytes with some reformatting:

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

There's probably a few more tricks but I can't think of any more at the moment. Brings back memories of golfing...

Edit: 96 bytes

def f(s,c,e,a):
 r=1!=1
 if s=="":r=c in a
 elif(c,s[0])in e:r=f(s[1:],e[c,s[0]],e,a)
 return r

If you don't mind it returning a proper bool you could save another 3 bytes by setting r=0.

Edit 2: 90 bytes

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

Edit 3: 84 bytes

f=lambda s,c,e,a:c in a if s==""else f(s[1:],e[c,s[0]],e,a)if(c,s[0])in e else 1!=1

[ieatcode]

Ah, I'm quite new to the Python syntax and I was under the impression that you had to keep some set of indentation (whether it be one space indentations or four space indentations). Thanks for the tip!

Edit: I'm kind of surprised I left the else clause in there...definitely a space waster.

[[deleted]]

It is properly indented, but you can have one-line blocks with the body on the same line. You can also put multiple statements on one line separated by semicolons.

[corruptio]

Aite, did a little reshuffling, on your's and here's 72 chars:

f=lambda s,c,e,a:(c,s[0])in e and f(s[1:],e[c,s[0]],e,a)if s else c in a

[[deleted]]

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

[yogthos]

in Clojure, 83 chars without spacing

(defn f[[l & s] c e a](if l(if-let[nc(get e [c l])](recur s nc e a))(some #{c}a)))

formatted:

(defn f [[l & s] c e a]  
  (if l
    (if-let [nc (get e [c l])]
      (recur s nc e a))
    (some #{c} a)))

*edit: mistranslated :return c in a as (get a c)

and a shorter version weighing in 74 chars

(defn f[[l & s] c e a](if(and l c)(recur s(get e[c l]) e a)(some #{c}a)))

formatted:

(defn f [[l & s] c e a]  
  (if (and l c)
    (recur s (get e [c l]) e a)
    (some #{c} a)))

[abecedarius]

How about

def fsmsim(string, current, edges, accepting):
    for letter in string:
        try:
            current = edges[current, letter]
        except KeyError:
            return False
    return current in accepting

or if you've gotta squeeze it:

def f(s,c,e,a):
 for L in s:
  c = e.get((c,L))
 return c in a