"On Certain Formal Properties of Grammars" (1959)
文字列の言語クラスについて Type-0, 1, 2, 3 という言語階層を明確にまとめた論文。ところで "Context-Free" という用語を最初に登場させたのは誰だろう？
このWiki内のページ
Grammar
G=<N,T,S,P>
- N : 非終端記号
- T : 終端記号
- S ∈ N : 開始記号
- P : α → β (α,β ∈ (N∪T)* の形の書き換え規則)
このオリジナル論文での各Typeの定義
- Type-0 : 制限無し
- Type-1 : αAβ → αωβ (ω≠"") の形の規則のみ許す（1文字ずつ、長さが広義単調増加）
- Type-2 : A → ω の形の規則のみ許す（文脈に依存した書き換えは駄目。ωは空でもいい）
- Type-3 : A → a か A → aB のみ許す（有限状態になるように）
示されていること
- Type-0 = Turing-Complete : well-known
- Type-3 ⊂ Type-2 ⊂ Type-1 ⊂ Type-0 の狭義包含
- Type-2 の "Chomsky Normal Form"。つまりルールの形は A→a と A→BC のみに制限できる。論文ではこの形式は "Regular"と呼ばれているけど正規言語のことではないので注意
- Type-3 は有限状態マシン（オートマトン）に等しい
- Type-2 が Type-3 でない iff 先頭/末尾でない再帰がある(self-embedding)
"Three Models for the Description of Language" (1956)
さらに少し前の論文。階層構造はそこまで明確になっていないけれど、生成文法 / Transformational Grammar の考え方の起源はここだと思う。Type-3 に対応する "Finite-State Grammar" と、Type-1/2 に対応する "Terminal Language" が登場。特記すべき事項として、非終端記号と終端記号の区別を付けないで生成される文字列全てを言語に含める "Derivational Language" という形式化も考えられている。DerivationalとFinite-StateがどちらもTerminalに含まれるが互いはuncomparableなことが示されている。この時点では
L-System系の形式化も考えられていたようだ。
最終更新：2009年04月07日 14:03
