當且僅當它是有限的，使得100 => n <= 0時，語言a^n b^2n是否是規則的可能性如何？

Question

語言a^n b^2n是否有規律，當且僅當它是有限的，使得100 => n < = 0？

我知道當n => 0時，這種形式的（a^nb^n）語言是不規則的，因爲我們需要一個臨時記憶來跟蹤a和b的數量，而且我知道每有限語言是規則的，但我不明白是什麼使有限的語言在一個相似的形式規則？我們如何證明它？我需要一些線索，除了能夠得到等值的正則表達式，我想要一些更詳細的解釋..

感謝名單

Answer 1

一個想法是想建一個正則表達式語言：

＆ε; ∪ ABB ∪ aabbbb ∪ aaabbbbbb ∪ ... ∪一個 b 。

你說得對，所有有限的語言都是規則的，而且由於這種特定的語言是有限的，所以它是規則的。

注意它的不當且僅當你限制的n，以便0 ≤ň≤ 100.相反，通過在限制增加形成的語言，0 ≤ñ≤ 100是有規律的這種語言是有規律的情況下。還有其他一些事情可以限制語言的使用，例如，您可以使用1,000或100,000的上限。