什麼意思是由免費的不常規的

Question

我正在準備免費的考試語法。我不明白爲什麼語言

{ a^n b^n | n>=0} 

是上下文無關，但不規則。爲什麼它不正常？ 什麼時候可以說表達式不規則？

由於

Answer 1

表達式是不正規，如果它不能被匹配（精確地）由regular expression或（等效地）一個finite state machine。另請參閱context free language和regular language。

Answer 2

那麼你可以說它是上下文無關的，因爲你可以使用上下文無關語法表達它。但它並不規則，因爲正則表達式（和有限自動機）不能表示該語言。

Answer 3

就像在前面的答案中說的那樣，它的上下文是免費的，因爲你可以用上下文無關文法來表達它。

例如：S -> aSb | ε

它不是常規的，因爲你不能用有限狀態機也正則表達式表達出來。您應該能夠計算As的數量並檢查該數量的Bs是否匹配。這不能用有限的狀態來完成作爲ñ可以是任何東西

Answer 4

的標準方法是使用Pumping Lemma