正規言語についての質問

正規言語について質問があります。

文字列を構成する文字を０か１とします。その時に０００を接頭辞とする言語が正規言語であることを確かめたいのですが、正規言語は決定性有限オートマトンで受理される言語であるので、０００を接頭辞とする言語を受理するオートマトンを構成しました。

以下のような決定性有限オートマトンを構成できるので、０００を接頭辞とする言語は正規言語であると考えましたが、正しいでしょうか？

オートマトンM=(K,Σ,δ,q0,F)において、Kを状態の集合、Σを入力文字の集合、δをK×Σ→Kの遷移関数、q0は初期状態、Fは受理状態の集合とします。

趣味で計算論を学んでいるので、基本的なところを間違えているかもしれませんが、教えてくれますと嬉しいです。よろしくお願いします。

No.3 ベストアンサー 回答者： Tacosan 回答日時： 2020/01/19 23:18

そんな感じ. 質問文でも受理状態ではループしてるから, これと同じことをすればいい.

最適化すると e, f, g は 1つにまとまるはずなのでそこまでやっていれば better.

この回答へのお礼

確かに遷移関数を考えたら１つにまとまりますね。何とかこの点に関しては理解できました。
ご回答ありがとうございました。

お礼日時：2020/01/19 23:33

No.2 回答者： Tacosan 回答日時： 2020/01/19 01:26

そうすると, 今度は

状態 e (など) で入力を受け取ったらどうするの?
って問題がでてくる.

状態 a, b, c で 1 が入力されたらそのあとはなにがどうあってもダメなのだから, 「ダメ」というブラックホールみたいな状態を 1つだけ作っておけばいい.

この回答へのお礼

素人の私に優しくご説明ありがとうございます。
＞「ダメ」というブラックホールみたいな状態を 1つだけ作っておけばいい.
δ(e,0)=δ(e,1)=e、δ(f,0)=δ(f,1)=f、δ(g,0)=δ(g,1)=gとしてループにして、a,b,cに1を入力した後は、0を入力しても1を入力しても状態は変化しないようにするということでしょうか？

お礼日時：2020/01/19 09:24

No.1 回答者： Tacosan 回答日時： 2020/01/18 23:54

空集合 φ は K の「要素」ではないので, δ の値にはできない. つまり

δ(a, 1) = φ
などとはできない.

逆に初期状態 q0 は K の要素でないといけないので, この場合 {a} と書いてはいけない.

この回答へのお礼

ご回答ありがとうございます。

もう一度考え直しましたが、非決定性でないので遷移先が１つもないことはないということを忘れていました。

φの代わりにa,b,cそれぞれの状態で1を入力された際に遷移する状態e,f,gを定義して

オートマトンM=({a,b,c,d,e,f,g},{0,1},δ,a,{d})として、遷移関数δを
δ(a,0)=b、δ(a,1)=e、δ(b,0)=c、δ(b,1)=f、δ(c,0)=d、δ(c,1)=g、δ(d,0)=δ(d,1)=d

と定めたら、目的の決定性有限オートマトンになりますでしょうか？

お礼日時：2020/01/19 01:19