DFA表示密码

Question

我想为具有以下约束的密码设计一个DFA：

• 它必须有8个字符长
• 它必须至少包含两个小写字符：[a-z]
• 它必须至少包含一个大写字符：[A-Z]
• 它必须至少包含两个十进制数：[0-9]
• 它必须至少包含以下一个特殊字符：[!.@*_]
• 它必须以一个特殊的字符开始。

我该如何设计这个DFA？

Answer 1

任何用于这种语言的DFA至少都需要记住。

• 已读取多少小写字母(0、1或2或更多)，
• 已读取多少大写字母(0或1或更多)
• 读取了多少小数位数(0、1或2或更多)。

这至少给了你至少18个州，而这甚至不考虑长度限制。我不认为你会为这种语言找到一个简单的DFA。它会很大的。

现在，您可以通过为每个限制构建一个DFA来构建一个非常简单但非常庞大的DFA (这些都不算太糟)，然后进行多方向的产品构建，为整个语言构建一个DFA。我认为这是理论上最优雅的方法，实际上在软件中表示这个非常容易。如果我真的要建造DFA，我就会这么做。