1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How do we choose between 1, 2, and 3? \$\endgroup\$ – Keith Randall Mar 24 '13 at 16:29
  • \$\begingroup\$ ...or do we write 3 separate programs? \$\endgroup\$ – Keith Randall Mar 24 '13 at 16:38
  • \$\begingroup\$ @KeithRandall the scoring indicates three programs are desired. \$\endgroup\$ – John Dvorak Mar 24 '13 at 16:47
  • \$\begingroup\$ Exactly, you have to produce three different programs, one for the DFA, one for the NFA and one for the epsilon-NFA. I chose to do so since they are stricly related(hence it doesn't make sense to ask 3 different questions). \$\endgroup\$ – Bakuriu Mar 24 '13 at 18:38
  • \$\begingroup\$ Can we get some example inputs / outputs? \$\endgroup\$ – boothby Mar 24 '13 at 20:08
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ i think you win \$\endgroup\$ – jdstankosky Apr 3 '13 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.