Implement DFA/NFA/epsilon-NFA

Question

Write the shortest code that implements a:

1. DFA
2. NFA
3. epsilon-NFA

The program should accept as input:

• a string(that we want to see if is accepted or not)
• the delta function, represented in whichever way it's more convenient.
• the "set" of final states of the automaton

And it should output Accepted! if the string is accepted by the automaton, and the string Not a chance! otherwise.

Note that all inputs should be taken from stdin or the command line.

The total points should be computed as (L1 + 2*L2 + 3*L3) / 6 where Li is the length, in bytes, of the code solving point i and the winner will be the answer with smallest score.

---

Edit: You can assume the starting state, so that it is not required as input.

The epsilon transitions can be labelled in any way you want.

---

Edit2: An example of input for the DFA:

0100
{'q_0': {'0': 'q_1', '1': 'q_0'}, 'q_1': {'0': 'q_2', '1': 'q_3'}, 'q_2': {'0': 'q_2', '1': 'q_3'}, 'q_3': {'1': 'q_0', '0': 'q_1'}}
{'q_2', 'q_3'}

Output:

Accepted!

An other input:

010010
{'q_0': {'0': 'q_1', '1': 'q_0'}, 'q_1': {'0': 'q_2', '1': 'q_3'}, 'q_2': {'0': 'q_2', '1': 'q_3'}, 'q_3': {'1': 'q_0', '0': 'q_1'}}
{'q_2', 'q_3'}

Output:

Not a chance!

I want to stress that you are free to use a different formatting for the inputs. Choose the simpler to "parse" in your target language. The above is simple to use in python since you can eval it to obtain the real objects.

Answer 1

Python, score = 138 1/6 = (79+108*2+178*3)/6

DFA

S,D,F=input()
s=1
for c in S:s=D[s,c]
print["Not a chance!","Accepted!"][F&s>0]

Input is a triple of string S, a delta function D, and final state mask F. I number each state with a power of 2, so F is just the OR of each accepting state. D is a map from (state,input char)->state.

example input (accepts all strings ending in b):

'abab',{(1,'a'):1,(1,'b'):2,(2,'a'):1,(2,'b'):2},2

NFA

S,D,F=input()
s=1
for c in S:
 t,s=s,0
 for a,b in D[c]:s|=t/a%2*b
print["Not a chance!","Accepted!"][F&s>0]

We number states as powers of 2 as before. D is a map from input character to a list of transitions labeled by that character.

example input (accepts all strings ending in b):

'abab',{'a':[(1,1)],'b':[(1,1),(1,2)]},2

epsilon-NFA

S,D,F=input()
E={1:1}
for i in D[0]:
 for a,b in D[0]:E[a]=a|E.get(b,b)
s=E[1]
for c in S:
 t,s=s,0
 for a,b in D[c]:s|=t/a%2*E.get(b,b)
print["Not a chance!","Accepted!"][F&s>0]

Same as NFA, but with the additional 0 character listing the epsilon transitions.

example input (accepts all strings ending in b):

'abab',{'a':[(1,1)],'b':[(1,1),(1,2)],0:[(2,4)]},2