非決定性有限オートマトン

決定性オートマトンは遷移先が1つに決定されていたが, 非決定性オートマトンは入力に対して複数の遷移先がある.

非決定性有限オートマトンの遷移関数は集合を返すので空集合を返すことがある.

非決定性有限オートマトンは受理するために都合の良い遷移を選んで良い.

｢どっちを選んでも受理されるような入力が来た時はどっちを選ぶんですか?｣ ｢どっちを選ぶかは重要ではなくて, 受理されるのかが重要｣

prologを思い出しました.

最終的に空集合を返すような遷移できないパターンも受理されたとは見做さない.

どの非決定性有限オートマトンにも等価な決定性有限オートマトンが存在する.

ε入力付非決定性有限オートマトン

入力を読まないという動作が追加された非決定性有限オートマトン. 入力を読まないという動作は入力εとして表す.

元の入力$Σ$と$\{ε\}$の直和$Σ ∪ \{ε\}$が入力になる. 当初先生は直積と言っていてまた頭の中で直和∪と直積∩がまた頭の中でごっちゃになってきてしまいました. やっぱり直和が正しいみたい. 資料に書かれているのも和集合ですし. 直和という訂正が入りました.

どのε入力付非決定性有限オートマトンにも等価な決定性有限オートマトンが存在する.