形式言語理論：第4回

• 実施日：2008-05-13（火）1限
• 講義内容：非決定性有限オートマトン（NFA）、ε-動作つき非決定性有限オートマトン（ε-NFA）
• 教科書2.3節、2.5.1〜2.5.3項

GW前にお話したDFAに引き続き、有限オートマトンの一種であるNFAとε-NFAについてお話しました。DFAとNFAの違いは、遷移関数の出力（次状態）が1状態であるか状態集合（0個以上の状態）であるか、です。またNFAとε-NFAの違いは、入力なしに状態遷移することを許すかどうか、です。見かけ上は差があるように見えますが、実はこれらは等価であることが分かっています。これらの結論とともに、サブセット構成法、模倣（simulation）という重要な考え方についてもお話しました。

教科書を受け取った人は2,800円をお支払いください。