构成 AGP 的语言的 FA
FA for a language which forms an AGP
假设一组输入符号 Σ={a,b} ，
L={ε,a,abbb,aabbbbbbbbb,aaabbbbbbbbbbbbbbbbbbb,...}
那么上述语言的有穷自动机（即构成一个简单的算术几何级数）将是？
这是非常规语言的一个很好的例子。直觉上，有限内存计算机要确定一个字符串是否在该语言中，它需要记住它看到了多少个 a，以便确定 b 的数量是否正确。不幸的是，对于多个 a 有无限多种可能的选择，而有限自动机无法记住无限多种不同选项中的一种。
您可以使用常规语言的泵引理或 Myhill-Nerode 定理来正式证明这一点。使用泵引理，选择一个像 a3n+1b3n 这样的字符串并证明泵a的数量打破了与b的数量的联系。对于 Myhill-Nerode 定理，选择形式为 a3n+1 的无限串族，并证明添加适合一个串的多个 b 会使另一个串不在语言。
假设一组输入符号 Σ={a,b} ， L={ε,a,abbb,aabbbbbbbbb,aaabbbbbbbbbbbbbbbbbbb,...}
那么上述语言的有穷自动机（即构成一个简单的算术几何级数）将是？
这是非常规语言的一个很好的例子。直觉上，有限内存计算机要确定一个字符串是否在该语言中，它需要记住它看到了多少个 a，以便确定 b 的数量是否正确。不幸的是，对于多个 a 有无限多种可能的选择，而有限自动机无法记住无限多种不同选项中的一种。
您可以使用常规语言的泵引理或 Myhill-Nerode 定理来正式证明这一点。使用泵引理，选择一个像 a3n+1b3n 这样的字符串并证明泵a的数量打破了与b的数量的联系。对于 Myhill-Nerode 定理，选择形式为 a3n+1 的无限串族，并证明添加适合一个串的多个 b 会使另一个串不在语言。