finite-automata - 定义字符串和绘制语言

Question

在 Σ = {A, B, C} 上定义的所有字符串的语言，它以 B 开头，以 A 结尾，最小长度为 3，并且还为该语言绘制有限自动机。

请用正则表达式的方式和语言图解释一下。在 Σ = {X, Y, Z} 上定义的所有字符串的语言，其中 Y 为第三个字母，Z 为倒数第二个字母

Answer 1

s -> Bx

x -> 是的 | 通过 | 赛

y -> 是的 | 通过 | 赛 | 一个

绘制有限自动机并不难。小写字母是状态，大写字母是输入符号。

状态“s”是开始状态。

从那里开始，单词以 B 开始，以状态“x”结束。

从“x”开始，输入可以是 A 或 B 或 C，并导致状态“y”。

从“y”开始，输入可以是 A 或 B 或 C，并返回“y”。输入 C 是特殊的，因为它可以/必须是单词的最后一个符号。所以 A 只是以完成状态结束（规则中没有明确提及）。

自动机看起来像这样：

识别所讨论语言的正则表达式如下：

B[ABC][ABC]*A- 或更短 -B[ABC]+A

在这种情况下，很容易（尤其是第一个正则表达式）看到自动机和正则表达式之间的对应关系。

---

Divyesh 的答案也几乎是正确的，他画了一个确定性自动机。您只需要删除到 q4 的过渡就可以了。

Answer 2

这个自动机一定是这个……