3

我将此 DFA 描述为 (Q, q1, A, N, F) 其中

Q = {1,2,3,4},
q1 = 1,
A = {a,b,c},
F = {2,4},
N = {
(1,a) -> 2, (1,b ) -> 3, (1,c) -> 4,
(2,a) -> 2, (2,b) -> 4,
(3,a) -> 2, (3,c) -> 4,
(4,b) -> 4, (4,c) -> 4 }

所以我画了转换图，看起来不错，

然后，我需要确定此 DFA 是否可以接受以下字符串：

  1. aabbcc
  2. 金合欢
  3. 卷心菜
  4. 巴巴布

并提出以下内容

  1. 正确的
  2. 不正确（不能从 a -> c 移动？）
  3. 不正确（不能从 c -a 移动？）
  4. 不正确（不能从 b -> a 移动）

我不是 100% 确定这些是正确的，但我认为它们在正确的轨道上。

然后我需要用英语描述它接受的语言，我认为这不是问题，但我需要帮助的地方是使用数学符号描述这种语言。你能帮我理解这一点吗？

非常感谢你的帮助

4

1 回答 1

0

您关于字符串可接受性的答案是正确的，这可以通过尝试在图表中遵循它们来轻松看出。
现在，关于语言：

在第二个顶点中，我们可以用下面的正则表达式对应的词来结束：
b?a+- 我们可以选择先获取b我移动到第三个顶点，然后传递a，或者我们可以一次移动到第二个顶点a，并且在那里我们可以添加尽可能多a的 s 。

现在关于完成第 4 个顶点中的单词：

首先，我们怎样才能到达顶点 4 ？
1. 我们可以通过c立即移动到第 4 个顶点，或者先移动到第 3 个顶点，得到 b，然后通过 到达第 4 个顶点c。因此，我们得到像 2 这样的字符串b?c
。我们可以到达顶点 2 b?a+（如前例所述），然后通过b. 因此，我们得到像b?a+b. 总的来说，我们可以使用任何匹配正则表达式
的单词到达第 4 个顶点。b?(a+b|c)

现在，在顶点 4 的末尾添加任意数量的b和c符号，我们得到了这种情况的答案：
b?(a+b|c)(bc)*

最后，我们可以得到这个 DFA 单词可接受的整个单词集，如下面的正则表达式：

b?( a+ | (a+b|c)(bc)*? )

于 2011-09-22T12:11:48.337 回答