形式言語とオートマトン - CIS授業wiki

形式言語とオートマトン･･･2年/CS/必修

lecture01 - 07/04/12

lecture02 - 07/04/19

lecture03 - 07/04/26

2007/04/26　17:19:15

NFA･･･非決定性オートマトン
　　　定義されないものがあってもよい！

ひとつの状態から矢印が２つ以上でられる。
何も入力されないときの矢印（λ）を書くことがある。
⇒使ったほうが簡単になることがある。
自由度が増したといえる。

コンピュータはDFAでなければだめ。

状態の多いものを考えたときに、
DFAだとよりtrickyに考えないとできない。しかも複雑になる。
（頭を使うということ）
一般に、これがNFAだともっと簡単にできる。
（なんたってエラーは最初から「定義されない」と返せばいいから）

λは何も入力がなかったとき、
または指定された入力がなかったときなど
指定以外のものをすべて含める。

だから同等なDFAとNFAを書くことができる。
（λ大活用！）

DFAとNFAを相互変換できる。
（問題をけっこう解かないと･･･その場では思いつかないかもしれない）

同じ状態のものはまとめることができる？
それかDFAをつくるときは｛｝とくくる？