オートマトン（正則表現について）

質問

カテゴリがよくわからなかったのでこちらで質問させていただきます。
今、オートマトンについて学んでいるのですが正則表現において同じ言語を
探す問題がよくわかりません。ちなみに問題は、
(0+1)*と同じ言語を表すのを探せという問題です。
これは0,1からなるすべての記号列の集合と書かれていました。
ちなみに選択肢は３つです。
(1)(1*+0*)(2)(1*+0)*(1+0)(3)(1+0*)(1*+0*)*1の３つです。

ちなみに演算の順番などはわかります。どのように同じ言語とみなすのかよくわかりません。
(0+1)*は(0*1*)*に直せるので任意個の0から始まり任意個の１が続く列が
任意個並んでいるという解釈を自分ではしています。あっているかはわかりませんが＠＠；）

それで他の選択肢もこのように直したりして見分けるのでしょうか？
後やはり0からはじまる列と1から始まる列や、
0で終わる列と1で終わる列では表すものはちがいますよね？
始めたばかりでまだ理解しきれていませんが
回答お願いします<(_ _)>

回答No.1

irija_bari · ベストアンサー

まず確認ですが、「+」の意味は、
(0+1) であれば、1個の0、または、1個の1という意味でしたよね？
（もう私の記憶は曖昧になっています。）

そうであれば、
>(0+1)*は(0*1*)*に直せるので任意個の0から始まり任意個の１が続く列が
>任意個並んでいるという解釈を自分ではしています。あっているかはわかりませんが＠＠；）
というのは、任意個というのが「0個以上」という意味でしたら、正しいです。
つまり、開始は 0 でも 1 でも良いということです。

>それで他の選択肢もこのように直したりして見分けるのでしょうか？
そのように考えても良いですし、
4つのオートマトンを状態遷移図にして、
・(0+1)* の状態遷移図と (1)～(3)の状態遷移図を比較する。
・(1)～(3)の状態遷移図に (0+1)* を入力してうまく遷移するかチェックする。
などという方法もあるのではないでしょうか。

>後やはり0からはじまる列と1から始まる列や、
>0で終わる列と1で終わる列では表すものはちがいますよね？
その通りです。

お礼

返信おくれてすみません。
なかなかイメージがわかないのですがどうにかやってみると３つとも
同じ言語を表していないようですね＠＠；
状態遷移図の書き方がいまいちよくわからないので
もう少し勉強してきます！
回答ありがとうございました。

回答No.2

irija_bari

ANo.1 です。補足です。

>なかなかイメージがわかないのですがどうにかやってみると３つとも
>同じ言語を表していないようですね＠＠；

1 つだけそれっぽいのがあるように思います。

まず、

>(0+1)*は(0*1*)*に直せるので任意個の0から始まり任意個の１が続く列が
>任意個並んでいるという解釈を自分ではしています。あっているかはわかりませんが＠＠；）

のような考え方で選択肢を解釈すると、明らかに 2 つは除外できます。

あとは、状態遷移図などを使って残りの 1 つと (0+1)* が一致するか確認してみてはいかがでしょうか。

同じ言語を表す異なる（正則表現での）記述を状態遷移図に書き直しても、なかなか一致させるのは難しいです。
（慣れないうちはなおさらだと思います。）

ある程度、あたりをつけてから状態遷移図などでチェックしていくと良いかもしれません。

お礼

回答ありがとうございます。
返信おくれました＠＠；
ん～状態遷移図ってなかなかイメージわきにくいんですよね～；；
また質問させて頂くかもしれませんがそのときはまた
よろしくお願いします<(_ _)>