請舉幾個是上下文無關文法而非正則文法的例子？

01-05

書上說，一個上下文無關語言是嚴格的，即不可能有正則文法產生，當且僅當該語言的一切文法都是自嵌套的。如果一切文法都是自嵌套的要如何產生全有終結符組成的語言呢？麻煩大家了，謝謝~

$L={ninmathbb{Z}^{+}:0^n 1^n}$ 就是啊……

證明：設 L 是正則語言，令 n 為 Pump lemma 的常數。選擇 $w=0^n1^n$ 則 $|w|ge n$

於是存在 x,y,z 使得 $w=xyz$ 並且 $|xy|le n,|y|ge 1,forall kge 0:xy^kzin L$

因為 $|xy|le n,|y|ge 1$ 那麼 y 中不包含 1 但是至少有一個 0

於是在 k = 0 時， $xy^kz=xz$ ，那麼 $xz$ 中 1 比 0 多，所以 $xz otin L$ ，和 Pump lemma 矛盾

因此 $L otin ext{REGULAR}$ . QED.

請問題主讀的是哪一本書？

最簡單的例子就是典型的嵌套配對括弧：

S -&> ( S ) | ε

S要麼是空串，要麼是嵌套在配對的括弧中的。

上面的B就是上下文無關非正則，證明可以根據DFA狀態是有限集合，利用https://en.wikipedia.org/wiki/Pumping_lemma 反證。

很多啊，DFA沒有棧，又不帶計數性，很多明確要求a數量b數量什麼的都不是正則文法，但很可能是上下文無關文法

龍書上的說法是「正則表達式不能計數」。

舉個栗子：

$L={a^{n}b^{n}|ngeq 1}$

正則表達式不能記錄在讀到第一個b之前a的個數，但是可以用文法

S→aAb A→aAb|ε

描述相同的語言。對於文法也有「一個文法可以對兩個個體進行計數，但是無法對三個個體進行計數」。