接頭辞文法

理論計算機科学と形式言語理論において、接頭辞文法は文字列書き換えシステムの一種であり、一連の文字列書き換え規則で構成され、形式文法や半Thueシステムに似ています。接頭辞文法の特徴は、規則の形ではなく、その適用方法にあります。つまり、接頭辞のみが書き換えられます。接頭辞文法は、すべての正規言語を正確に記述します。^[1]

正式な定義

接頭辞文法Gは3要素組（Σ、S、P ）であり、

Σは有限のアルファベットである
SはΣ上の基本文字列の有限集合である
Pは、 u → vという形式の生成規則の有限集合であり、uとvはΣ上の文字列である。

文字列x、yに対して、文字列u、 v、 wが存在して⁠ ⁠、かつv → wがPに含まれる場合、 x → _G yと記述します（また、G は1 ステップでxからyを導出できるとも言えます）。 $\to$ $G は$ Σ の文字列上の2 項関係であることに注意してください。 $x=vu,y=wu$

Gの言語は⁠ ⁠と表記され、 Sから0 回以上のステップで導出可能な文字列の集合です。正式には、S内のいくつかのsに対してs R wとなる文字列wの集合です。ここで、R は $\to$ $G$ の推移閉包です。 $L(G)$

例

接頭辞文法

Σ = {0, 1}
01, 10 のとき
P = {0 → 010, 10 → 100}

正規表現で定義された言語を記述する

01(01)^{*}\cup 100^{*}

参照

規則的な文法

参考文献

^ M. FrazierとCD Page。接頭辞文法：正規言語の別の特徴づけ。Information Processing Letters、51(2):67–71、1994年。

[1] M. FrazierとCD Page。接頭辞文法：正規言語の別の特徴づけ。Information Processing Letters、51(2):67–71、1994年。