「形式言語理論」第10回

• 実施日: 2007-06-26(火) 1限
• 講義内容: プッシュダウンオートマトン
• 教科書6.1節, 6.1.1〜6.1.2項

今回はプッシュダウンオートマトンを紹介しました。直観的には、プッシュダウンオートマトンはスタックを1本持つ非決定性の有限機械であり、文脈自由文法と等価な言語表現能力を持ちます。有限オートマトンと異なり，プッシュダウンオートマトンには、受理する言語の定義が2通りあります。入力を読み切ったとき(1)受理状態にたどりついていれば受理(2)スタックが空になっていれば受理、というものです。

次回はこの講義の最終回として、この2つの受理の定義が等価であること、そしてプッシュダウンオートマトンと文脈自由文法が等価であること、この2点について説明をします。