將L = {a * b *}劃分爲常規語言嗎？

Question

將L = {a * b *}分類爲常規語言嗎？

我很困惑，因爲我知道L = {a^n b^n}不規則。克萊恩明星有什麼不同？

Answer 1

當你有一個L = {a^n b^n}和一個L = {a*b*}這是有區別的。

當你有一個a^n b^n語言它是你必須具有相同數量a's和b's例子的語言：{aaabbb, ab, aabb, etc}。正如你所說，這不是一個正則表達式。

但是，當我們談論L = {a*b*}這是有點不同，在這裏你可以有任何數量的a後跟任何數字的b（包括0）。有些例子是：

{a, b, aaab, aabbb, aabbbb, etc} 

正如你可以看到它是從那裏你需要有a's和b's相同號碼{a^n b^n}語言不同。

並且是a*b*其性質是固定的。如果你想有一個很好的解釋爲什麼它是有規律的，你可以檢查此How to prove a language is regular他們可能有一個更好的解釋，然後我（：

我希望它幫你

Answer 2

由正則表達式b是描述語言這些表達式不能描述任何非正規語言，並且確實是定義正規語言的方式之一。

{a^nb^n：n> 0}（這將是一種正式完整的方式描述它），不能用正則表達式來描述。直觀地，當到達a和b之間的邊界時，你需要記住n。由於它不受限制，所以沒有有限存儲器件可以做到這一點。在b你只需要記住從現在起只有b應該出現;這是非常有限的。這兩顆星在某種意義上是不相關的;每個獨立擴展其塊。