不收縮文法

形式定義[編輯]

在形式語言理論中，文法是不收縮的（或單調的），如果所有它的產生規則都有如下形式

α -> β 這裏的 |α| ≤ |β|，|α| 指示 α 的長度。

就是說，沒有規則會減少被重寫的字符串的大小。

它是本質不收縮的，如果可有一個例外，也就是，規則

S → ε

這裏的 S 是開始符號而 ε 是空串。

S → abc

S → aSBc

cB → Bc

bB → bb

這個文法生成語言 $\{a^{n}b^{n}c^{n}:n\geq 1\}$ ，它不是上下文無關的。

還有給語言 $\{a^{n}b^{n}c^{n}d^{n}:n\geq 1\}$ 的（更加複雜）的不收縮文法。

有容易的過程把任何不收縮文法轉換成 Kuroda範式。

已知把任何不收縮文法變換成上下文有關文法或反之的過程。

所以，不收縮文法，Kuroda 範式的文法，和上下文有關文法有同樣的表達能力。

更精確地說，不收縮文法精確的描述不包含空串的上下文有關語言，而本質不收縮文法精確的描述上下文有關語言的集合。