世界大百科事典(旧版)内のプッシュダウンオートマトンの言及
【形式言語】より
…この言語の構造は((…()…))で表される入れ子構造である。文脈自由言語はプッシュダウンオートマトンによって識別され,その族は,正規言語の族を真に含む。
[文脈規定文法]
Σの有限個の要素からなる2つの記号系列をu,vとするとき,書き換え規則の形がu→vで,しかもvの長さがつねにuの長さ以上であるとき,この文法をさ文脈規定文法context sensitive grammar,あるいは1型文法という。…
※「プッシュダウンオートマトン」について言及している用語解説の一部を掲載しています。
出典|株式会社平凡社「世界大百科事典(旧版)」