关于有限状态自动机的问题
我想构造一个确定性有限自动机，它接受以下语言：
{w ∈ {a,b}* ：w 中的每个 a 前面紧接着 ab}
到目前为止，我已经得到 >⨀ ---b---> O---a---> O.
“>” = 初始状态
⨀ = 最终状态
I want to construct a deterministic finite automata that accepts the following language:
{w ∈ {a,b}* : each a in w is immediately preceded by a b}
So far I've got >⨀ ---b---> O ---a---> O.
'>' = initial state
⨀ = final state
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
思考 FA 的一个好方法是尝试思考你可以处于多少种不同的情况，即你将如何获得语言中的字符串。让我们从一些小字符串开始，看看我的意思。
假设您从空字符串开始。您可以在其中附加什么来获取该语言的字符串？好吧，空字符串在语言中，所以我们可以附加空字符串（即什么都没有），并且在语言中也有一个字符串。此外，我们可以将我们要查找的语言中的任何字符串附加到空字符串中，然后我们将得到该语言中的字符串（简单地）。我们至少需要一种状态来记住空字符串（以及类似的字符串 - 我们可以将空字符串或该语言中的任何其他字符串附加到的字符串，并且该语言中仍然有一个字符串）；这将是开始/初始状态，并且由于空字符串在语言中（我们很容易检查这一点），我们知道开始/初始状态将被接受。
现在让我们考虑字符串 a。这是一个不在该语言中的字符串的示例，我们无法在该字符串的末尾添加任何内容以使其成为该语言中的字符串；我们已经违反了字符串中所有 a 前面都有 b 的条件。我们可以添加到此以获取该语言中的字符串的字符串集是空集，因此，我们需要一个与我们已经识别的状态不同的状态来记住该字符串和类似的字符串 - 其字符串我们无法添加任何内容来获取该语言中的字符串。
回顾一下，我们已经确定了两种状态：接受开始/初始状态，以及我们所说的“死”状态 - 一种不接受并且永远不会导致接受状态的状态。
我们来试试字符串 b。该字符串是语言中的，因此我们可以向其中添加空字符串。我们还可以简单地将语言中的任何其他字符串添加到该字符串的末尾，并获取该语言中的另一个字符串。但是，我们也可以添加 a 后跟该语言中的任何字符串，并获得该语言中的另一个字符串。例如，我们可以将字符串 a 后跟 bbabb 相加，得到 babbabb，这也是语言中的。因此，我们可以添加的字符串集合是我们以前从未见过的集合，并且我们需要一个新的状态来表示该字符串 - 字符串 b - 以及类似的字符串。它将被接受，因为字符串 b 是该语言中的字符串。
您应该尝试字符串 aa、ab、ba 和 bb。你应该发现字符串 aa 和 ab 都已经被我们的死亡状态覆盖了（我们不能在它们的末尾添加任何字符串来获取我们语言中的任何内容），并且字符串 ba 被开始/初始覆盖state（我们只能添加该语言中已有的字符串来获取该语言中的其他字符串），并且 bb 对应于我们确定的第三个状态（添加任何字符串或单个 a 后跟任何字符串，将导致字符串也在该语言中）。由于我们已经用尽了所有长度为 2 的字符串并且没有添加任何新状态，因此我们知道这些都是我们在 FA 中需要的状态；我们可以添加其他的，但它们是不必要的。
为了实现转换，我们需要做的就是确保所有状态都指向正确的位置。换句话说，由于字符串a是在空字符串末尾添加字符a形成的，所以我们需要从start/initial状态（对应空字符串）到dead状态（对应字符串a）的转换。 ) 当 FA 读取符号 a 时发生。类似地，我们需要符号 b 上从开始/初始状态到第三状态的转换。其他转换的情况类似：在 a 或 ab 上，死状态转换到自身，第三状态在 b 上循环并转换到 a 上的开始/初始状态。一旦每个状态都有字母表中每个符号的转换，您就拥有了完整（且正确）的 FA。此外，通过以这种方式构建它，您可以保证拥有一个最小的 FA...这是解决需要一个 FA 的问题的好方法，而不是提出一个任意的 FA 并事后将其最小化。
A good way to think about FAs is by trying to think about how many different situations you can be in, in terms of how you are going to get to a string in the language. Let's start with a few small strings and see what I mean.
Say you start with the empty string. What can you append to this to get a string in the language? Well, the empty string is in the language, so we can append the empty string (i.e., nothing) and also have a string in the language. Additionally, we can append any string in the language we are going for to the empty string, and we will get a string in the language (trivially). We will need at least one state to remember the empty string (and strings like it - strings to which we can append the empty string or any other string in the language and still have a string in the language); this will be the start/initial state, and since the empty string is in the language (we check this easily), we know the start/initial state will be accepting.
Now let's consider the string a. This is an example of a string not in the language, and there's nothing we can add to the end of this string to cause it to be in the language; we've already violated the condition that all a's in the string are preceded by b's. The set of strings we can add to this to get a string in the language is the empty set, and therefore, we will need a state distinct from the one we've already identified to remember this string and strings like it - strings to which we cannot add anything to get a string in the language.
To recap, we have identified two states: an accepting start/initial state, and what we call a "dead" state - a state that is not accepting and which does not ever lead to an accepting state.
Let's try the string b. This string is in the language, and so we can add the empty string to it. We can also trivially add any other string in the language to the end of this string, and get another string in the language. However, we can also add an a followed by any string in the language, and get another string in the language. For instance, we can add the string a followed by bbabb to get babbabb, which is also in the language. The set of strings which we can add is therefore a set we haven't seen before, and we will need a new state to represent this string - the string b - and strings like it. It will be accepting, since the string b is a string in the language.
You should try the strings aa, ab, ba, and bb. You should find that the strings aa and ab are both already covered by our dead state (we can't add any strings to the end of these to get anything in our language), and that the string ba is covered by the start/initial state (we can only add to this strings already in the language to get other strings in the language), and that bb corresponds to the third state we identified (adding any string, or a single a followed by any string, will result in a string also in the language). Since we have exhausted all strings of length 2 and not added any new states, we know that these are all the states that we need in the FA; we could add others, but they'd be unnecessary.
To get the transitions, all we need to do is to make sure that all the states lead to the correct place. In other words, since the string a is formed by adding the character a to the end of the empty string, we need a transition from the start/initial state (corresponding to the empty string) to the dead state (corresponding to the string a) which occurs when the FA reads the symbol a. Similarly, we need a transition from the start/initial state to the third state on the symbol b. The other transitions are found similarly: on either an a or a b, the dead state transitions to itself, and the third state loops on b and transitions to the start/initial state on an a. Once each state has a transition for each symbol in the alphabet, you have a complete (and correct) FA. Moreoever, by constructing it in this fashion, you guarantee that you have a minimal FA... which is a nice way to solve problems requesting one, instead of coming up with an arbitrary one and minimizing it post-hoc.
状态 1（接受，初始状态）：
状态 2（接受）：
状态 3（不接受）
从概念上讲，状态 1 表示“一个有效字符串，其最后一个字母不是 b”，状态 2 表示“最后一个字母是 b 的有效字符串”，状态 3 表示“无效的字符串”
以图形形式表示：
State 1 (accepting, initial state):
State 2 (accepting):
State 3 (not accepting)
Conceptually, State 1 represents "a valid string whose final letter is not b", State 2 represents "a valid string whose final letter is b", and State 3 represents "a string that is not valid"
In graphed form: