形式言語理論：第6回

• 実施日：2008-05-27（火）1限
• 講義内容：正則表現→DFA、正則表現の代数的性質
• 教科書3.2.1節、3.4節

正則表現のしめくくりとして、前回残っていた正則表現からDFAを構成する方法、および正則表現の代数的性質についてお話しました。正則表現からDFAを構成する方法は割と技巧的で、教科書の証明を読んだだけでは分かりにくいかもしれません。講義では、かなり直観的な解説を試みたつもりです。

正則表現も式ですから、交換則、結合則、分配則など、比較的なじみのある代数的性質が成り立ちます。ただ、一般に正則表現の式変形はあまり簡単ではありません。特に閉包が絡むと途端に式変形が難しくなります。そのため、工学的には、有限オートマトンを経由するほうが簡単です。4章で、このための基本的な手法である状態数最小化について述べます。