オートマトンとチューリング機械 - hagiya laboratory

《オートマトンとチューリング機械 - hagiya laboratory》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、オートマトンとチューリング機械有限オートマトン有限オートマトン有限個の状態現在の状態初期状態受理状態入力文字列有限個の文字…アルファベット状態遷移入力文字と現在の状態に従って、現在の状態をかえる。状態遷移図101001二進数を、0と1から成る文字列として入力し、3の余りを計算する有限オートマトン初期状態言語アルファベット有限個の文字の集合Σなどで表す。例：Σ={0,1}文字列（語）アルファベットに属する文字の有限列例：0,00,1100,0101空列も文字列。εやλで表す。文字列の全体をΣ*で表す。言語（形式言語）文字列の集合、すなわちΣ*の部分集合。例：3で割り切れる二進数の全体言語の認識装

2、置としての有限オートマトン状態のいくつかを受理状態とする。受理状態は複数あってもよい。与えられた文字列に従って、初期状態からはじめて状態遷移を繰り返す。初期状態は一つ。文字列を読み終わった直後の状態が受理状態ならば、その文字列を受理。有限オートマトンMが受理する文字列の全体をL(M)と書く。L(M)をMの受理言語という。有限オートマトン1010013で割り切れる二進数の全体を受理する有限オートマトン初期状態受理状態でもある。有限オートマトン101000初期状態110と1を奇数個ずつ含む文字列を受理するオートマトン正則表現言語を表す記法文字列のパターンを表す。例：0(10)*10で始まり10が

3、繰り返されて1で終わる文字列そういう文字列からなる言語例：0(11+00)10の次に11または00が来て、1で終わる文字列例：0(11+00)*1正則表現から有限オートマトンへ正則表現⇒有限オートマトン任意の正則表現に対して、その言語を受理する非決定的な有限オートマトンが存在する。決定化非決定的な有限オートマトンは、受理言語が同じ決定的なオートマトンに変換できる。最小化決定的なオートマトンは、受理言語をかえずに状態数が最小化できる。有限オートマトン⇒正則表現正則言語非決定的な有限オートマトン10ε初期状態0011ε遷移：文字を入力せずに遷移できる。非決定的な有限オートマトン10初期状態0011

4、01受理状態に至る遷移のしかたが一つでもあればよい。決定的な有限オートマトン10初期状態00110決定的な有限オートマトン0初期状態10011110010状態数最小の有限オートマトン0初期状態100111001有限オートマトンの性質受理言語の合併、交わり、補集合、連接、閉包などに関して閉じている。任意のM1とM2に対して、L(M1)∪L(M2)=L(M)となるMが存在する。二つのオートマトンが受理する言語が同じかどうかを判定することができる。数を数えられない：有限オートマトンの限界例えば、0と1を同じ数だけ含む文字列のみを受理する有限オートマトンは存在しない。チューリング機械チューリング機械ヘ

5、ッド有限状態制御部テープチューリング機械の動作有限状態制御部の状態と、ヘッド上の文字の各組み合わせに対して、ヘッドが書き込む文字（同じ文字をかけば無変化）次の状態（文字を書いた後に）ヘッドを左右のどちらに動かすか、動かさないか。という動作を定義。動作が一通りに定まらないものは、非決定的なチューリング機械チューリング機械の停止停止状態を定めることもある。次の動作が定義されなかったら停止。場合によっては、停止しないこともある。言語の認識装置としてのチューリング機械入力文字列をテープ上に書き込み、書き込む前は空白文字が埋まっている。テープには、入力文字列に現れる文字以外の文字を書き込んでもよい。入

6、力アルファベット⊂テープ・アルファベットヘッドを最初の文字の上におき、状態を初期状態にセットして、機械を走らせる。停止したら、その文字列を受理。受理状態において停止したら、とすることもある。チューリング機械と計算可能性言語の認識装置として入力アルファベット上の言語Lが、チューリング機械Mによって認識できるとき、その言語を帰納的に可算という。Mを用いれば、与えられた文字列がLに属しているとき、有限時間内にそのことがわかる。Lに属していないときは、Mは止まらないかもしれないので、そのことはいつまでたってもわからないかもしれない。以上のような認識が、計算の限界である。チャーチのテーゼチューリング機械

7、M01101受理or不受理（or非停止）入力文字列ww∈Lw∈L帰納的に可算vs.帰納的入力アルファベット上の言語Lが、常に停止するチューリング機械Mによって認識できるとき、その言語を帰納的いう。Mを用いれば、与えられた文字列がLに属しているとき、有限時間内にそのことがわかる。Lに属していないときも、有限時間内にそのことがわかる。言語Lとその補集合がどちらも帰納的に可算ならば、L（およびその補集合