不收縮文法

在形式語言理論中，文法是不收縮的（或單調的）

基本介紹

• 中文名：不收縮文法
• 學科：計算機

形式定義

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

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

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

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

• S → ε
  

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

例子

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

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

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

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

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

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

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

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

形式語言

在數學、邏輯和計算機科學中，形式語言（英語：Formal language）是用精確的數學或機器可處理的公式定義的語言。

如語言學中語言一樣，形式語言一般有兩個方面:語法和語義。專門研究語言的語法的數學和計算機科學分支叫做形式語言理論，它只研究語言的語法而不致力於它的語義。在形式語言理論中，形式語言是一個字母表上的某些有限長字元串的集合。一個形式語言可以包含無限多個字元串。