Implement DFA/NFA/epsilon-NFA
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&amp;s&gt;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&amp;s&gt;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&amp;s&gt;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