计算机科学问题理论

Question

我正在研究计算机科学的理论问题，但遇到了一些困难：

a. 给出一个非确定性有限自动机（NFA），它能识别语言 (01 ∪ 001 ∪ 010)^*

b. 将这个NFA转换成一个等价的确定性有限自动机（DFA）。只给出从起始状态可达的DFA部分。

我正在使用 automata.fa 这个包来编码自动机并进行测试。这里有一些示例：

# example DFA syntax
example_dfa = DFA(
    states={'q1', 'q2', 'q3', 'q4', 'q5'},
    input_symbols={'0', '1'},
    transitions={
        'q1': {'0': 'q1', '1': 'q2'},
        'q2': {'0': 'q1', '1': 'q3'},
        'q3': {'0': 'q2', '1': 'q4'},
        'q4': {'0': 'q3', '1': 'q5'},
        'q5': {'0': 'q4', '1': 'q5'}
    },
    initial_state='q3',
    final_states={'q3'}
)

# example NFA syntax
example_nfa = NFA(
    states={"q0", "q1", "q2"},
    input_symbols={"0", "1"},
    transitions={
        "q0": {"": {"q1", "q2"}},
        "q1": {"0": {"q1"}, "1": {"q2"}},
        "q2": {"0": {"q1"}, "1": {"q2"}},
    },
    initial_state="q0",
    final_states={"q1"},
)

# example regular expression syntax
example_regex = "(a*ba*(a|b)*)|()"

针对上面的问题，我尝试用以下的NFA图：

from automata.fa.nfa import NFA

prob_1_17a = NFA(
    states={'q0', 'q1', 'q2', 'q3'},
    input_symbols={'0', '1'},
    transitions={
        'q0': {'0': {'q3'}, '1': {'q0'}},
        'q1': {'0': {'q1'}, '1': {'q0'}},
        'q2': {'0': {'q0'}, '1': {'q2'}},
        'q3': {'0': {'q1'}, '1': {'q2'}},
    },
    initial_state='q0',
    final_states={'q0'}
)

但是自动评分系统给出了以下输出：

结果：

运行命令：

$ timeout 15 python3 unit_tests/unit_test_prob_1_17a.py

在这些输入上出现了意外结果：

['01', '00101', '01001', '01010', '010101', '00100101', '00101001', '00101010', '01000101', '01001001', ...]

测试：unit_test_prob_1_17a.py

这个测试让你多得了0分

如何设计正确的NFA/DFA？

Answer 1

你尝试的这个非确定性有限自动机（NFA）可以这样理解：

不过，这个设计是不对的。比如，它允许输入以1开头，但这个语言是不允许的。在状态q₂的循环会让输入出现连续的1，但这是不可能的。状态q₁的循环则允许输入有任意数量的0，但这个语言永远不接受有四个或更多连续0的字符串。

另一方面，你的设计不接受有效的输入"01"，因为在输入这样的字符串后，状态会变成q₂，而这个状态在你的NFA中并不是接受状态。

如何设计NFA

为了设计一个符合语言(01 ∪ 001 ∪ 010)^*的NFA，我们可以一步一步来。首先设计一个语言(01)^*的图示：

这里q₀是起始状态和接受状态，而q₄是无效输入的终止状态。接着扩展到(01 ∪ 001)^*：

最后完成到(01 ∪ 001 ∪ 010)^*：

如何从NFA设计DFA

为了设计一个对应的确定性有限自动机（DFA），我们需要为NFA中每一个可能的状态组合定义一个状态。例如，(₁,₂)就是一个这样的状态，而(₀,₁,₂)是另一个。这样的状态有很多，但只有一些是真正可达的。

通过使用幂集构造法，我们可以识别哪些输入前缀会导致NFA中的哪些状态，并为每个唯一的状态组合分配一个不同的DFA状态。一旦我们发现一个与之前遇到的前缀相同的NFA状态组合，就不需要再延长这个前缀了，因此我们得到了以下可能性的表格：

前缀	NFA状态	DFA状态
ε	0	0
0	1,2	12
00	1	1
000	4	4
001	0	0
01	0,3	03
010	0,1,2	012
0100	1,2	12
0101	0,3	03
011	4	4
1	4	4

我为DFA的状态选择了反映它们如何映射到NFA状态组合的名称。每个对应于包含₀的NFA状态组合的DFA状态都是接受状态。

这就得到了以下的DFA：

Python代码

上面的NFA和DFA可以用以下方式表示：

nfa = NFA(
    states={'q0', 'q1', 'q2', 'q3', 'q4'},
    input_symbols={'0', '1'},
    transitions={
        'q0': {'0': {'q1','q2'}, '1': {'q4'}},
        'q1': {'0': {'q4'},      '1': {'q0'}},
        'q2': {'0': {'q1'},      '1': {'q3'}},
        'q3': {'0': {'q0'},      '1': {'q4'}},
        'q4': {'0': {'q4'},      '1': {'q4'}} # Sink
    },
    initial_state='q0',
    final_states={'q0'}
)

dfa = DFA(
    states={'q0', 'q1', 'q12', 'q03', 'q012', 'q4'},
    input_symbols={'0', '1'},
    transitions={
        'q0'  : {'0': 'q12',  '1': 'q4' },
        'q12' : {'0': 'q1',   '1': 'q03'},
        'q1'  : {'0': 'q4',   '1': 'q0' },
        'q03' : {'0': 'q012', '1': 'q4' },
        'q012': {'0': 'q12',  '1': 'q03'},
        'q4':   {'0': 'q4',   '1': 'q4' } # Sink
    },
    initial_state='q0',
    final_states={'q0', 'q03', 'q012'}
)