「形式言語理論」第4回

• 実施日: 2007-05-01(火) 1限
• 内容: DFAとNFAの等価性、FAの応用(テキスト検索)
• 教科書2.4.3節まで

前半では、言語クラス、等価性、模倣（simulation）の話をしました。いずれも教科書ではあまりはっきり書かれていませんが、この講義の内容を理解する上で基本となる考え方なので、丁寧に話してみました。「ある」言語／DFA／NFA／…と「すべての」言語／DFA／NFA／…の違いに充分注意しておいて下さい。

教科書を申し込まれた方は、次回の講義時に2,734円を釣り銭のないように持ってきて下さい。