finite-automata - FA 用于形成 AGP 的语言

Question

假设一组输入符号 Σ={a,b} , L={ε,a,abbb,aabbbbbbbbb,aaabbbbbbbbbbbbbbbbbb,...}

那么上述语言的有限自动机（即形成一个简单的算术几何级数）将是？

Answer 1

这是非常规语言的一个很好的例子。直观地说，有限内存计算机要确定一个字符串是否属于该语言，它需要记住它看到了多少个 a，以便它可以确定 b 的数量是否正确。不幸的是，对于许多 a 有无限多可能的选择，而有限自动机无法记住无限多不同的选择之一。

您可以通过使用常规语言的泵引理或 Myhill-Nerode 定理来正式证明这一点。使用抽水引理，选择像³ⁿ⁺¹ b ^{3 n}这样的字符串，并证明抽水 a 的数量会断开与 b 数量的联系。对于 Myhill-Nerode 定理，选择形式为 a ³ⁿ⁺¹的无限字符串族，并表明为一个字符串添加多个 b 会使另一个字符串不在该语言中。