「形式言語理論」第8回

• 実施日: 2007-06-12(火) 1限
• 内容: DFAの状態数最小化、文脈自由文法
• 教科書4.4節、5.1節

長らくかかった有限オートマトンの話の最後として、DFAの状態数最小化アルゴリズムについてお話しました。理論的にも実用的にも興味深いものなので、アルゴリズム、これによって何が嬉しいのか、等の点について知っておくと後々役に立つこともあるかと思います。

次のトピックとして、文脈自由文法とプッシュダウンオートマトンを取り上げます。文脈自由文法については学部講義の「コンパイラ」でもお話しましたので、今回はその復習がてら、どのようなものであったかをざっとお話ししました。残り回数が少々心配になってきたので、この講義では、文脈自由文法と構文木（「コンパイラ」では解析木と言っていたもの）の関連、そして文脈自由文法と等価なオートマトンであるプッシュダウンオートマトンとの関連について、主にお話していこうと思っています。