grammar - 这个确定性有限自动机的语言是什么？

Question

鉴于：

我不知道公认的语言是什么。

通过查看它，您可以获得几个最终结果：

1.) bb
2.) ab(a,b)
3.) bbab(a, b)
4.) bbaaa

Answer 1

如何为 DFA 编写正则表达式

在任何自动机中，状态的目的就像记忆元素。一个状态以自动方式存储一些信息，如 ON-OFF 风扇开关。
确定性有限自动机（DFA）称为有限自动机，因为有限数量的内存以状态的形式存在。对于任何正则语言 (RL)，DFA 始终是可能的。

让我们看看 DFA 中存储了哪些信息（参考我的彩色图）。
（注意：在我的解释中，任何数字都表示零次或多次，并且Λ是空符号）

---

State-1：是START状态，存储的信息是偶数个 a 。和零 b。
此状态的正则表达式 (RE) 是= (aa)*。

状态 4：奇数a已经到来。和零b。
此状态的正则表达式是= (aa)*a。

图：蓝色状态=偶数 个，红色状态=奇数a个 已经来了 。a

注意：一旦第一个b已经到来，移动不能回到状态 1 和状态 4。

状态 5：在 之后Yellow b。Yellow b 意味着 b after odd numbers of a。
一旦你得到b奇数个a（在状态5），一切都是可以接受的，因为在状态5有一个（b，a）的循环。

您可以为 state-5 编写：Yellow-b 后跟 a、b 的任何字符串，即= Yellow-b (a + b)*

State-6：只是为了区分奇数a还是偶数。

状态 2：甚至在a任何b数量的b. = (aa)* bb*

State-3：在 state-2 之后，a然后在 state-6 之后有一个循环。我们可以为 state-3 来写= state-2 a (aa)* = (aa)*bb* a (aa)*

因为在我们的 DFA 中，我们有三个最终状态，所以 DFA 接受的语言是三个 RL（或三个 RE）的并集（RE 中的 +）。
所以 DFA 接受的语言对应三个接受状态 2,3,5，我们可以这样写：

 State-2 +  state-3           + state-5    

(aa)*bb* + (aa)*bb* a (aa)*+Yellow-b (a + b)*

我忘了解释how Yellow-b comes?
答案：Yellow-b是b状态4或状态3之后。我们可以这样写：

Yellow-b = ( state-4 + state-3 ) b = ( (aa)*a+ (aa)*bb* a (aa)*)b

[答案]
(aa)*bb* + (aa)*bb* a (aa)*+ ( (aa)*a+ (aa)*bb* a (aa)*)b (a + b)*

---

英语 语言描述: DFA 接受三种语言的联合

• 偶数个a，后跟一个或b多个，
• 偶数个a，后跟一个或b多个，奇数个a。
• 一个前缀字符串and a，b带有奇数a个's，后跟，b后跟任何and字符串 a。bΛ

英语描述很复杂，但这是描述语言的唯一方法。您可以通过首先将给定的 DFA 转换为最小化的 DFA 然后编写 RE 和描述来改进它。

---

此外，还有一种衍生方法可以使用Arden 定理从给定的转换图中找到 RE 。我在这里解释了如何使用 Arden's theorem 为 DFA 编写正则表达式。必须首先将转换图转换为没有空移动和单启动状态的标准形式。但我更喜欢通过分析学习计算理论，而不是使用数学推导方法。

Answer 2

我想这个问题不再相关了:) 引导你完成它然后只是陈述答案可能会更好，但我想我有一个涵盖它的基本表达式（它可能是最小化的），所以我就写它为未来的搜索者准备

(aa)*b(b)* // for stoping at 2
U
(aa)*b(b)*a(aa)* // for stoping at 3
U
(aa)*b(b)*a(aa)*b((a)*(b)*)* // for stoping at 5 via 3
U
a(aa)*b((a)*(b)*)* // for stoping at 5 via 4

Answer 3

您提供的示例（1 - 4）不是DFA 接受的语言。它们只是属于DFA 接受的语言的字符串。因此，它们都属于同一种语言。

如果你想找出定义 DFA 的正则表达式，你需要做一些叫做k-path 归纳的事情，你可以在这里阅读它。