关于有限状态自动机的问题

Question

我想构建一个接受以下语言的确定性有限自动机:

{w∈{a,b}*:w中的每个a前面都有ab}

到目前为止,我已经>⨀--- b ---> O --- a ---> O.

'>'=初始状态

⨀=最终状态

Answer 1

考虑FAs的一个好方法是尝试考虑你将如何使用该语言中的字符串来处理多少种不同的情况.让我们从几个小字符串开始,看看我的意思.

假设你从空字符串开始.您可以在此处添加什么来获取该语言的字符串？好吧,空字符串是在语言中,所以我们可以附加空字符串(即什么都没有),并且在语言中也有一个字符串.另外,我们可以将我们要使用的语言中的任何字符串附加到空字符串中,并且我们将获得该语言的字符串(通常).我们将需要至少一个状态来记住空字符串(和它一样的字符串 - 我们可以在其中附加空字符串或字符串中的任何其他字符串并且仍然在该语言中包含字符串的字符串); 这将是开始/初始状态,由于空字符串是语言(我们很容易检查),我们知道开始/初始状态将接受.

现在让我们考虑字符串a.这是一个不在语言中的字符串示例,我们无法添加到此字符串的末尾以使其处于语言中; 我们已经违反了字符串中所有字符都以b开头的条件.我们可以添加到这个以获取语言中的字符串的字符串集是空集,因此,我们将需要一个与我们已经识别的字段不同的状态来记住这个字符串和类似它的字符串 - 字符串我们无法添加任何东西来获取语言中的字符串.

回顾一下,我们已经确定了两种状态:接受开始/初始状态,以及我们称之为"死"状态 - 一种不接受并且不会导致接受状态的状态.

我们来试试字符串b.此字符串使用的是语言,因此我们可以将空字符串添加到其中.我们还可以将语言中的任何其他字符串添加到此字符串的末尾,并在该语言中获取另一个字符串.但是,我们还可以在语言中添加一个a后跟任何字符串,并在该语言中添加另一个字符串.例如,我们可以添加字符串a后跟bbabb来获取babbabb,这也是语言.我们可以添加的字符串集是一个我们以前没见过的集合,我们需要一个新的状态来表示这个字符串 - 字符串b - 和类似的字符串.它将接受,因为字符串b是该语言中的字符串.

你应该尝试字符串aa,ab,ba和bb.您应该发现字符串aa和ab都已经被我们的死状态所覆盖(我们不能在这些字符串的末尾添加任何字符串以获取我们语言中的任何内容),并且字符串ba由start/initial覆盖state(我们只能在语言中添加这些字符串以获取语言中的其他字符串),并且bb对应于我们识别的第三个状态(添加任何字符串,或者单个a后跟任何字符串,将导致字符串也在语言中).由于我们已经耗尽了所有长度为2的字符串并且没有添加任何新状态,我们知道这些都是我们在FA中需要的所有状态; 我们可以添加其他人,但他们没有必要.

要获得转换,我们需要做的就是确保所有状态都能到达正确的位置.换句话说,由于字符串a是通过将字符a添加到空字符串的末尾而形成的,因此我们需要从开始/初始状态(对应于空字符串)到死状态(对应于字符串a)的转换)当FA读取符号a时发生.类似地,我们需要在符号b上从开始/初始状态到第三状态的转换.可以类似地找到其他转换:在a或ab上,死状态转换为自身,第三状态在b上循环并转换为a上的开始/初始状态.一旦每个州都有一个字母表中每个符号的转换,您就有一个完整的(正确的)FA.无论如何,通过以这种方式构建它,你保证你有一个最小的FA ...这是一个很好的方法来解决请求一个问题,而不是提出一个任意的,并在事后最小化它.