计算机科学问题理论

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)*)|()"

对于上述问题，我尝试用下图来表示NDA：

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

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

q₀是开始和接受状态，q₄是无效输入的接收器。然后扩展到(01 ∪ 001)^*:

然后补全到(01 ∪ 001 ∪ 010)^*:

要设计相应的 DFA，请为 NFA 中每个可能的状态集定义一个状态。例如 (𝑞₁,𝑞₂) 就是这样一种状态，而 (𝑞₀,𝑞₁,𝑞₂) 是另一种状态。这样的状态有很多，但真正可达的只有一些。

使用 powerset 构造，我们可以识别哪些输入前缀导致 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'}
)