为什么{a ^ na ^ n | n> = 0}是否正常？

Question

我了解原因和{a^n b^n | n >= 0}不正常的证明。 为什么{a ^ nb ^ n | n> = 0}是否不规则？

我的一项练习的解决方案是：{a^n a^n | n >= 0}定期进行。我如何证明这一论点？

Answer 1

是的，语言{a ⁿ a ⁿ | n> = 0} 是常规语言。为了证明某些语言是正规的，您可以绘制其dfa /正规表达式。您可以按以下方式为此语言驱动do：

因为“ for ”与“ for n> = 0”相同，并且这是“所有偶数个符号的字符串竞赛的集合” ，所以它是正则表达式-正则表达式为。anann >= 0a2na(aa)*

注意，正则表达式仅适用于正则语言，因此证明了{a ⁿ a ⁿ | n> = 0}是常规语言。而DFA为：

我建议您阅读这本书，为什么{a ⁿ b ⁿ | n> = 0}不是常规的。