跳至內容

不收縮文法

維基百科,自由的百科全書

形式定義

形式語言理論中,文法不收縮的(或單調的),如果所有它的產生規則都有如下形式

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

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

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

S → ε

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

例子

S → abc
S → aSBc
cB → Bc
bB → bb

這個文法生成語言 ,它不是上下文無關的。

還有給語言 的(更加複雜)的不收縮文法。

等價的文法類型和表達能力

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

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

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

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

參見