实施DFA/NFA/epsilon-NFA

Question

编写实现以下内容的最短代码：

1. DFA
2. NFA
3. 埃普西隆-NFA

程序应接受作为输入：

• 字符串(我们希望查看是否被接受)
• δ函数，以更方便的方式表示。
• 自动机最终状态的“集合”

如果该字符串被自动机接受，它应该输出Accepted!，而字符串Not a chance!则不然。

注意，所有输入都应该从stdin或命令行中提取。

总分应计算为(L1 + 2*L2 + 3*L3) / 6，其中Li是代码解题点i的长度(以字节为单位)，获胜者将是得分最小的答案。

编辑:您可以假设开始状态，所以它不需要作为输入。

epsilon跃迁可以以任何你想要的方式被标记。

Edit2: 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'}

输出：

Accepted!

另一项投入：

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'}

输出：

Not a chance!

我想强调的是，您可以对输入使用不同的格式。选择目标语言中更简单的“解析”。上面的内容在python中很容易使用，因为您可以eval它来获得真实的对象。

Answer 1

Python，得分= 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]

输入是字符串S、增量函数D和最终状态掩码F的三重结构。我用2的幂对每个状态进行编号，所以F只是每个接受状态的OR。D是来自(state，input )->state的映射。

示例输入(接受以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]

我们像以前一样将状态数为2的幂。D是从输入字符到标记为该字符的转换列表的映射。

示例输入(接受以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]

与NFA相同，但附加的0字符列出了epsilon转换。

示例输入(接受以b结尾的所有字符串)：

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