爲什麼是{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星號（*））的基元。現在你完成了。