DFA构建

Question

我仍然在掌握有限自动机的诀窍，我目前还停留在这个例子上(这是一个未评分的学习指南，供所有想知道的人参考)。我对如何实现DFA来解决这个问题感到困惑……我想我的主要问题是如何计算输入了多少个字符，以及是否达到了所有其他限制……

You must construct passwords from the following alphabet
{a,b,c,A,B,C,0,1,2} with the these additional constraints:

valid passwords must be at least 5 characters long
they must contain at least one lower-case letter
they must contain at least one upper-case letter
and they must contain at least one digit.

Design a DFA accepting only valid passwords. 

Answer 1

你需要同时满足4个条件，

让我们将条件称为P、Q、R和S

• P：接受的字符串必须至少为5个字符long
• Q：接受的字符串必须至少包含一个小写letter
• R：接受的字符串必须包含至少一个大写的letter
• S：并且必须至少包含一个数字。

无论其他条件如何，每个条件都可以是真或假。

如果我们用1表示true，用0表示false，我们得到16种不同的可能性，我们可以使用真值表(为了易读性而分组)来可视化：

P | Q | R | S
---------------

0   0   0   0
0   0   0   1
0   0   1   0
0   0   1   1

0   1   0   0
0   1   0   1
0   1   1   0
0   1   1   1

1   0   0   0
1   0   0   1
1   0   1   0
1   0   1   1

1   1   0   0
1   1   0   1
1   1   1   0
1   1   1   1

让我们用q[0, 0, 0, 0]表示第一行，第二行用q[0, 0, 0, 1]表示，依此类推。我们实际上不会使用所有的状态，特别是

1   0   0   0
1   0   0   1
1   0   1   0
1   0   1   1
1   1   0   0
1   1   0   1
1   1   1   0

将保持未使用状态。然而，我们将需要一个在真值表中没有语义等价的额外状态。我们将这种状态称为Foo。稍后会详细介绍这一点。

现在，我们必须指定每个状态的转换，以及确定我们的初始状态。

对于每个状态，必须描述每个输入字符的转换。让我们采用这样的符号：

q[0, 0, 0, 0] ---ABC--> q[0, 0, 1, 0]

这意味着当我们处于q[0, 0, 0, 0]状态时，我们读取A、B或C中的任何字符，我们执行上面的状态转换。

现在，我将只展示最终DFA的一部分，因为我们可以使用它作为模板来组成解决方案的其余部分。

q[0, 0, 0, 0]是我们的初始状态，对于输入"ABC“，我们得到

q[0, 0, 0, 0] ---ABC--> q[0, 0, 1, 0]

我们现在已经读到了一个大写字母。从这里有三种可能性，我们读另一个大写字母并保持相同的状态：

q[0, 0, 1, 0] ---ABC--> q[0, 0, 1, 0]

或者我们读取一组数字或一组小写字母：

q[0, 0, 1, 0] ---012--> q[0, 0, 1, 1]
q[0, 0, 1, 0] ---abc--> q[0, 1, 1, 0]

然后，对于任何一种状态，我们都可以继续使用到目前为止遇到的所有输入，即。那

q[0, 0, 1, 1] --ABC012--> q[0, 0, 1, 1]

和

q[0, 1, 1, 0] --ABCabc--> q[0, 1, 1, 0]

现在，如果我们在状态q[0, 0, 1, 1]中，读到一个小写字母，我们得到状态q[0, 1, 1, 1]，类似地，如果我们在状态q[0, 1, 1, 0]中，读到一个数字，我们最终得到q[0, 1, 1, 1]。在这一点上，我们已经读取了3个或更多字符！

现在，来自

q[0, 1, 1, 1]

在到达接受状态之前，我们需要读取两个字符。在这里，我将使用"X“来表示”任何东西，只要它是集合{0，1，2，a，b，c，A，B，C}中的一个字符“。

因此，从q[0, 1, 1, 1]中，我们可以获得以下转换序列

q[0, 1, 1, 1] -- X --> Foo -- X --> q[1, 1, 1, 1]

在q[1, 1, 1, 1]中，我们可以做到这一点

q[1, 1, 1, 1] -- X --> q[1, 1, 1, 1]

我们可以这样设想所有这些转换(我决定在这一点上省略逗号，以减少在小屏幕设备上换行的风险)，

                               ABCabc loops back here
                                         |
                                         V
                            +--abc--> q[0110] --012--+
                            |                        |
                            |                        V
 q[0000] --ABC--> q[0010] --+                     q[0111]-- X -- Foo -- X --> q[1111]
                  |     ^   |                        ^
                  |     |   |                        |
                  +-ABC-+   +--012--> q[0011] --abc--+
                                         ^
                                         |
                               ABC012 loops back here

如果我们从012开始，我们就会得到

                               012abc loops back here
                                         |
                                         V
                            +--abc--> q[0101] --ABC--+
                            |                        |
                            |                        V
 q[0000] --012--> q[0001] --+                     q[0111]-- X -- Foo -- X --> q[1111]
                  |     ^   |                        ^
                  |     |   |                        |
                  +-012-+   +--ABC--> q[0011] --abc--+
                                         ^
                                         |
                               ABC012 loops back here

所以有一个对称性，当第一个结构是"abc“时，我们可以创建一个类似的结构。这就是饼干崩溃的方式。