-
無限制文法
鎖定
- 中文名
- 無限制文法
- 又 稱
- 0型文法
- 學 科
- 數學
無限制文法簡介
無限制文法形式定義
無限制文法是形式文法
，這裏的N是非終結符的集合，
是終結符的集合，這裏的
和
是無交集的(實際上這個限制不是必需的，因為無限制文法在非終結符和終結符之間不做真實區分，存在這個指定純粹是為了使得你在嘗試生成文法的句子形式的時候知道何時停止)，P是形如
的產生規則的集合，這裏的
和
是在 中的符號的字符串而
是非空字符串，
是特別指定的開始符號。如名稱所暗含的，在無限制文法可以有什麼類型的產生規則上沒有真實限制。
無限制文法無限制文法和圖靈機
可以證明無限制文法特徵化了遞歸可枚舉語言。這同於聲稱對於所有無限制文法G都存在某個圖靈機有能力識別
反之亦然。給定一個無限制文法，這種圖靈機足夠簡單構造為兩磁帶非確定圖靈機。第一個磁帶包含要被測試的輸入字W，而機器使用第二個磁帶生成來自G的句子形式。圖靈機接着做如下事情:
開始於第二個磁帶的左端並重復的選定要右移或選擇在磁帶上的當前位置。
非確定的從G中選定一個產生式
。
如果
出現在第二個磁帶的某個位置，在這個點上把
替代為
，依據
和 的相對長度可能要把在磁帶上的符號向左或右移動(就是説如果
長於
，左移磁帶符號)。
比較在磁帶 2 上的結果句子形式和在磁帶 1 上的字。如果匹配，則圖靈機接受這個字。如果不匹配則回到步驟 1。
容易看出這個圖靈機將在最後步驟被執行任意次之後在第二個磁帶上生成G的所有的句子形式，所以語言
必定是遞歸可枚舉的。
無限制文法計算性質
從無限制文法和圖靈機的等價性上，給定一個字符串
是否屬於某個無限制文法的語言的決定性問題一般是不可判定的。
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：7次歷史版本
- 最近更新： smile路过倾城