NFA 接受最后一位数字之前未出现过的语言

Question

给出一个接受以下语言的非确定性有限自动机（NFA）： 字母表 {0,1,...,9} 上的字符串集合，其中最后一个数字之前未出现过。 我在自动机理论语言和计算简介第67页练习2.3.4中遇到了这个问题

Answer 1

当字母表为 {0,1} 时，这是最简单的非平凡情况，我们可以得到一个最简单的 NFA，如下所示：
最简单的非平凡情况
因此，您还可以获得这样的 NFA：
在此处输入图片说明

Answer 2

获得 NFA 的一个简单方法是分别考虑这 10 种情况。考虑最后一位数字为 0 的语言中所有字符串的情况。此类字符串不包含其他 0；它们的正则表达式是 (1+2+3+4+5+6+7+8+9)*0。他们的 NFA 看起来有点像

  1,2,3,4,5,6,8,9
       /--\
       |  /
       V /
o----->A0--0-->[B0]

我们可以想象另外 9 个状态为 Ax、Bx，其中 Bx 接受每个 x，并且 Ax 在除 x 之外的每个符号上循环到自身，并在符号 x 上循环到 Bx。

然后，我们可以通过引入一个新的初始状态 S 将所有这些粘合在一起，该初始状态 S 具有到 Ax 状态的空/lambda 转换。最终的 NFA 将具有：

• 一个初始状态 S
• 空/lambda/epsilon 从 S 转换到状态 A0、A1、A2、A3、A4、A5、A6、A7、A8 和 A9
• 在 0、A1 到 B1 上从 A0 转换到 B0在 1 上，从 A2 到 B2 在 2 上，依此类推
• 从状态 A0、A1、A2 等所有缺失的转换返回到那些相同的状态

事实上，为什么不呢复制/粘贴上面的内容然后写下整个内容？

       1,2,3,4,5,6,7,8,9
            /--\
            |  /
            V /
     /----->A0--0-->[B0]
    /
   |   0,2,3,4,5,6,7,8,9
   |        /--\
   |        |  /
   |        V /
   | /----->A1--1-->[B1]
   |/
   |   0,1,3,4,5,6,7,8,9
   |        /--\
   |        |  /
   |        V /
   | /----->A2--2-->[B2]
   |/
   |   0,1,2,4,5,6,7,8,9
   |        /--\
   |        |  /
   |        V /
   | /----->A3--3-->[B3]
   |/
   |   0,1,2,3,5,6,7,8,9
   |        /--\
   |        |  /
   |        V /
   | /----->A4--4-->[B4]
   |/
   /   0,1,2,3,4,6,7,8,9
S-<         /--\
   \        |  /
   |\       V /
   | \----->A5--5-->[B5]
   |
   |   0,1,2,3,4,5,7,8,9
   |        /--\
   |        |  /
   |\       V /
   | \----->A6--6-->[B6]
   |
   |   0,1,2,3,4,5,6,8,9
   |        /--\
   |        |  /
   |\       V /
   | \----->A7--7-->[B7]
   |
   |   0,1,2,3,4,5,6,7,9
   |        /--\
   |        |  /
   |\       V /
   | \----->A8--8-->[B8]
   |
   |   0,1,2,3,4,5,6,7,8
   |        /--\
   |        |  /
    \       V /
     \----->A9--9-->[B9]

这是该语言最简单的 NFA 或 DFA 吗？几乎可以肯定不是。但它应该有效。