为什么是{a^n a^n | n> = 0}定期？

Question

我了解原因和证明为什么{a^n b^n | n >= 0}不正常。 Why is {a^nb^n | n >= 0} not regular?

我的一个练习的解决方案是：{a^n a^n | n >= 0}是正常的。我怎样才能证明这个论点？

Answer 1

是，语言{a ⁿ a ⁿ | n> = 0} 是一种常规语言。为了证明某种语言是正规的，你可以绘制它的dfa /正则表达式。你可以驾驶这种语言做如下：

因为“anan为n >= 0”是同为“a2n对于n> = 0”，那就是“设置偶数符号a的所有字符串竞赛” 正则表达式 —正则表达式为(aa)*。

注意，正则表达式仅可用于常规语言，因此证明了{一^ň一个^ñ | n> = 0}是一种常规语言。和DFA是：

我建议你阅读本why languages like {aⁿ bⁿ | n >= 0} are not regular。

Answer 2

首先将定义更改为等效L = {a^2n | n >= 0}。现在观察属于L的任何字符串只是2的一个倍数。然后将该定义更改为(aa)*，这是一个正则表达式，因为它仅使用表示常规语言（个别字符（a），级联（aa）和Kleene星号（*））的基元。现在你完成了。