构造一个FA（自动机理论）

Question

您需要为所有长度为奇数的字符串构造一个有限自动机，但在字母表{a，b}上包含偶数个b。

我已经这样做了

((a+b)(a+b))*bb+bb*((a+b)(a+b)) 

，但我知道这是错的，那么，什么是这个问题的答案？

Answer 1

你说你正在寻找一个自动机，但你的（错误的）答案是一个正则表达式。我会提供一个自动机。它使用两个计数器mod 2;一个为长度，一个为b的数量。所以各州是：

q[0,0], q[0,1], q[1,0], q[1,1] 

例如， q [0,1]意味着总数是偶数（第一个零），而b的数目是奇数（一个）。所以最终状态是q [1,0]，而q [0,0]是初始状态。

的转换是相当明显的，做了柜台进行必要的修改：

q[0,0] reads a -> q[1,0] 
q[0,0] reads b -> q[1,1] 
q[0,1] reads a -> q[1,1] 
q[0,1] reads b -> q[1,0] 
q[1,0] reads a -> q[0,0] 
q[1,0] reads b -> q[0,1] 
q[1,1] reads a -> q[0,1] 
q[1,1] reads b -> q[0,0]