寻找不确定的有限自动机语言

Question

我是一名计算机科学专业的二年级学生，我们得到了一个不确定的有限自动机，并询问它接受什么词。

我尝试将其简化为确定性有限自动机，结果如下：

我认为它不接受 b* 或 a 或 a(b+ab*a)* 格式的任何单词，无法弄清楚它们之间的共同点以及它接受的单词，我想这个这么多，它与整个单词无关，只与开头相关，因为如果单词以 aa 开头，它可以有 a 和 b 的任意组合，并且它会被接受。

非常感谢您的帮助。

Answer 1

首先，我会用我自己的方式来回答这个问题。然后，我将解决您转换为确定性有限自动机的问题。

我们可以编写一组方程式并求解 q2 以查看导致该状态的正则表达式。考虑以下系统：

(q1) = (q2)a + e
(q2) = (q1) + (q3)(a + b)
(q3) = (q1)a + (q3)b

我们要解决是什么导致接受状态，所以我们先排除非接受状态：

(q1) = (q2)a + e
(q2) = (q2)a + e + (q3)(a + b)
(q3) = (q2)aa + a + (q3)b

要消除 (q3) 我们可以使用规则 (x) = r + (x)s <=> (x) = rs* 然后代入：

(q1) = (q2)a + e
(q3) = ((q2)aa + e)b*
(q2) = (q2)a + e + ((q2)aa + a)b*(a + b)
     = (q2)a + e + (q2)aab*(a + b) + ab*(a + b)
     = (q2)[a + aab*(a + b)] + [e + ab*(a + b)]
     = (e + ab*(a + b))(a + aab*(a + b))*
     = (e + ab*(a + b))(a(e + ab*(a + b)))*

我们恢复的正则表达式基本是这样描述的：

Get to q2 either by taking the empty transition, or going through q3; then, get back to q2 by going to q1 and repeating the first part. You can do this as many times as you want.

你是怎么写系统的？

e可以达到初始状态
如果在表达式 r 上存在从状态 q 到状态 q' 的转换，则 q' = (q)r
如果可以通过多种方式到达某个状态，请使用 + 并包括所有方式

要确定有限自动机，请考虑状态的每个子集并在进行时添加转换。我们从仅包含初始状态的子集 {q1} 开始。

  /------------------------------------\
  |                               __   |
  V                              /  \  |
{q1} -a-> {q1,q3} -a-> {q1,q2,q3}   a  |
 |           |             |     ^__/  |
 b           b             b           |
 |     __    |             |           |
 V    /  V   V             |           |
{ }   b   {q2,q3} <--------/           |
 ^    \__/      \                      |
 |               \-a->{q1,q2}-----a----/
 |                     |               
 \----------b----------/

添加状态和转换的规则是：

始终添加初始状态{qi}
对于每个状态 {q1,q2,...,qn} 和输入字母表中的每个符号 x，添加从 {q1,q2,...,qn} 到 {q1',q2' ,...,qn'} 在 x 上，其中 q1', q2', …, qn' 可以从 q1, q2, …, qn 通过恰好消耗一个 x（可能还有几个 e-transitions）
如果状态 {q1',q2',...,qn'} 不在您的自动机中，请添加它，然后对该状态重复此过程
重复上述操作，直到添加了所有必要的状态，并且所有状态对输入字母表中的每个符号都有转换。

注意：在上面的自动机中，我没有显示死状态{}上的转换。源自死状态的所有转换都以死状态终止。

我的{q1}类似于你的最上面（OK）。我的 { } 类似于您的 HOLE。我的 {q1,q3} 类似于您的 NOT。我的{q2,q3}类似于你最右边的OK

但是 - 我的 {q1,q2,q3} 与您最底层的 OK 不同。为了让你的像我的一样，在符号 b 上添加从最底部的 OK 到最右边的 OK 的过渡。

注意我的{q1,q2}是多余的，等同于我的{q1}；从 {q1,q2} 出来的所有转移都和从 {q1} 出来的转移一样。真的，因为从 q1 到 q2 的电子转换，我应该让 {q1,q2} 成为初始状态，但无论如何 - 你明白了。

你的 DFA 不可能正确的原因是在 NFA 中，总是有机会 "blow it" 并最终陷入困境。在你的自动机中，你可以到达最底部的OK然后被设置。

寻找不确定的有限自动机语言

Finding nondeterministic finite automaton language

computer-science

computation