此确定性有限自动机是什么语言？

Question

给出：

<< img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9pLnN0YWNrLmltZ3VyLmNvbS9scU9LeC5qcGcifQ==” alt =“在此处输入图像描述”>

我不知道接受的语言是什么。

通过查看，您可以得到一些最终结果：

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

Answer 1

如何为DFA编写正则表达式

在任何自动机中，状态的目的就像存储元素。状态会自动存储一些信息，例如风扇开关。确定性有限自动机（DFA），称为finite自动机，因为有限内存量以状态形式存在。对于任何常规语言（RL），始终可以使用DFA。

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

---

State-1：

是START状态，并且存储在其中的信息是偶数a已经到来。而且[零 b。此状态的正则表达式（RE）为= (aa)*。

State-4：

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

Figure：

a BLUE状态= EVEN数量a，而RED状态= ODD数量[C0 ]来了。

NOTICE：

一旦出现第一个[[b

，就无法回到状态1和状态4。 State-5：在a之后。Yellow b

均值

Yellow b。一旦在状态5的奇数[[b after odd numbers of a之后得到b，则所有事物都是可以接受的，因为状态5处的（b，a）本身存在一个循环。 您可以为状态5编写：黄色-b，后跟a，b的任何字符串，该字符串为[[=aYellow-bState-6：只是要区分是奇数[[(a + b)*还是偶数。

State-2：

紧接着是[[a然后是[[a然后是任意数量的

b。 =b(aa)*

State-3：

在状态2之后，然后是首先bb*，然后是通过状态6的循环。我们可以为状态3来写=astate-2a=(aa)*(aa)*bb* a因为在我们的DFA中，我们有三个最终状态，所以DFA接受的语言是三个RL（或三个RE）的并集（RE中的+）。因此DFA接受的语言对应于三个接受的[[states-2,3,5

，我们可以这样写：(aa)*[ State-2 + state-3 + state-5 +(aa)*bb*(aa)*bb*a+(aa)*Yellow-b

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

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

[ANSWER

]b+(aa)*bb*(aa)*bb*a+（(aa)* +(aa)*a(aa)*bb* a）(aa)* b

语言的英语描述
：DFA接受三种语言的结合

[C0]

的偶数，后跟一个[(a + b)*的一个或多个，

偶数[C0]，后跟一个或多个

---

a，后跟奇数数[b。

[[a和b的前缀字符串，奇数为

a，后跟
• a，后跟任何字符串b AND a AND
• b。
英语描述很复杂，但这是描述语言的唯一方法。您可以通过以下方法进行改进：首先将给定的DFA转换为最小化的DFA，然后编写RE和说明。

[还有一种推导方法，可以使用a从给定的过渡图中查找RE。我已经在这里解释了b。首先必须将过渡图转换为没有零移动和单启动状态的标准形式。但是我更喜欢通过分析学习计算理论，而不是使用数学推导方法。

Answer 2