形式言語理論：第5回

• 実施日：2008-05-20（火）1限
• 講義内容：ε-NFA（受理言語の定義、DFAとの等価性）、正則表現（定義、正則表現からε-NFAへの変換）
• 教科書2.5.4〜2.5.5項、3.1節、3.2.3項

前回途中になってしまったε-NFAの話を終わらせた後、正則表現について話を始めました。

ε-NFAの受理言語やDFAとの等価性は、ほぼNFAの場合と同じです。唯一違うのは、入力なしで遷移できる状態達を考慮しなければならないという点です。そこで ε-閉包（ε-closure）という概念を導入し、受理言語の定義、およびε-閉包を考慮したサブセット構成法について説明しました。

正則表現の定義については、学部講義「コンパイラ」でもかなりちゃんとお話しています。この講義では、「コンパイラ」で触れなかった話題を中心に話を進めていきます。まず取り上げるのは、有限オートマトンとの等価性です。今日は時間の都合で、与えられた正則表現から等価なε-NFAを構成するアルゴリズムについてのみ説明しました。次回は、与えられたDFAから等価な正則表現を構成するアルゴリズムについて説明をします。