需要字母表 {a,b} 的 DFA，使得该语言必须包含相等且偶数的 a 和 b

Question

偶数个和b的DFA是这个但是偶数个和相等个数的a和b的DFA不可用 L={ psilon,aabb,abab,baba,bbaa,aaaabbbb,aabbaabb,bbaabbaa,babababa,ababababa,bbbbaaaa,........}

我是目录新手，请用简单的答案指导我

Answer 1

仅当给定语言是“常规”语言时，您才能为该语言设计 DFA。您上面描述的语言不是常规语言。因此，你无法为其设计 DFA（或 NFA 或正则表达式）。 上述语言的非正则性的证明是通过使用著名的泵引理（对于正则语言）：假设

相反

该语言（称为 L）是正则的。令 p 为由泵浦引理给出的泵浦长度。令 s 为字符串 a^{2p}b^{2p}。因为这个串是L的成员，并且长度大于p，泵送引理保证它可以分成三段，s = xyz，满足引理的三个条件；但这个结果实际上是不可能的：块 y 仅由 a 组成，即 y=a^k (k >= 1)。所以，xz = xy^0z = a^{2p-k}b^p 不在 L 中。