形式言語理論：第7回

• 実施日：2008-06-03（火）1限
• 講義内容：正則言語の性質
• 教科書4.1〜4.3節を抜粋

前回までお話した正則言語（有限オートマトンで受理される言語、正則表現で表される言語）の性質についてお話をしました。ただし、4章は、理論的には興味深いが現実の応用には結びつきにくい話も含まれているため、内容を抜粋しながらお話しています。教科書は比較的平易に書いてありますので、理論に興味を持っている方は一読してみるとおもしろいと思います。

お話したのは、反復補題（4.1節）、集合和・補集合・共通部分に関する閉包性（4.2節）、正則言語に関する空集合判定問題や所属性問題（4.3節）です。結論そのものとともに、証明の考え方も知っておいてほしいと思います。