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

Question

鉴于:

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

从它看,你可以得到几个最终结果:

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

Answer 1

如何为DFA编写正则表达式

在任何自动机中,状态的目的就像记忆元素.状态存储自动化中的一些信息,如ON-OFF风扇开关.
确定性有限自动机(DFA)称为有限自动机,因为有限量的存储器以状态的形式存在.对于任何常规语言(RL),DFA始终是可能的.

让我们看看存储在DFA中的信息(参考我的彩色图).
(注意:在我的解释中,任何数字表示零次或多次,并且?为空符号)

状态-1:是START状态,存储在其中的信息是偶数 a .并且ZERO b.
该状态的正则表达式(RE)是= (aa)*.

状态-4:奇数a已经到来.并且ZERO b.
此状态的正则表达式为= (aa)*a.

图: 一个BLUE状态= EVEN数目的a,和 RED状态= ODD的数目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)*

状态-6:区分是奇数a还是偶数.

状态-2:即使在a那b之后,任何数量的b.= (aa)* bb*

状态-3:在状态-2之后,然后首先a是状态-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.
• 前缀字符串a和b与奇号a的,BY FOLLOWED b,其次是任何字符串a和b和?.

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

此外,有一个导数方法使用Arden的Therm从给定的Transition Graph中找到RE 我在这里解释了如何使用Arden定理为DFA编写正则表达式.首先必须将转换图转换为没有空移动和单启动状态的标准形式.但我喜欢通过分析而不是数学推导方法来学习计算理论.