正規表現とオートマトンについての問題です。

解決済

質問者：inoue824
質問日時：2014/01/06 03:27
回答数：1件

正規表現とオートマトンについての問題です。
下記の決定性有限オートマトンMが受理する言語L（M)を正規表現で表したい。以下のカタカナ

に入る記述を穴埋めしなさい。

状態iから状態ｊに、kより大きな数字の状態を通らないで遷移させる入力文字列の集合をkRij

と表すと、一般的に、
kRij = k-1Rik(k-1Rkk)*k-1Rkj∪k-1Rijと表される。

そこで、L(M)とは、初期状態1から受理状態3へ3より大きな数字の状態を通らないで遷移させる

入力文字列の集合のことであるから、
L(M) = ア = 2R13(2R33)*2R33∪2R13 ・・・・・(1)
と書ける。(1)式は2R13でくくると、
L(M) = 2R13((2R33)*イ∪ウ) ・・・・・(1')
となるが、一般に文字列集合をAとするとき、
A* = エ∪A1∪A2∪A3∪ ・・・と定義され、
A*A = (オ∪A1∪A2∪A3∪ ・・・ )A
= A1∪A2∪A3∪A4∪ ・・・となり、
従って、A*A∪{ε} = A*A ∪ A0 = A* ・・・・・(2)
である。よって(1')式は、
L(M) = 2R13(2R33)* ・・・・・(1'')
と簡単化される。(1'')式の、まず2R13を求める。
2R13 = カ(1R22)*キ∪1R13
ここで、ク = 0R11(0R11)*0R12∪0R12 = {ε}{ε}*{1}∪ケ = コ
1R22 = 0R21サ0R12∪0R22 = シ{ε}*{1}∪{ε,1} = {ε,1}
1R23 = 0R21(0R11)*0R13∪0R23 = φ{ε}*ス∪{0} = {0}
1R13 = 0R11(0R11)*0R13∪セ = {ε}ソ{0}∪タ = チ

故に 2R13 = ツ{ε,1}*{0}∪テ

ここで、{ε,1}* = トだから
2R13 = {1}ナ{0}∪{0} = ({1}ニ∪{ε}){0} ・・・・・(3)

次に2R33については
2R33 = ヌ(1R22)*1R23∪1R33
ここで、ネ = 0R31ノ0R12∪0R32 = φ{ε}*{1}∪φ = ハ
1R33 = 0R31(0R11)*0R13∪0R33 = φ{ε}*{0}∪{ε,ヒ} = {ε,フ}
故に 2R33 = φ{ε,1}*{0}∪{ε,0}=ヘ

従って(1'')式は、(3)(4)式から
L(M) = ({1}ホ∪{ε}){0}{ε,0}*
上式()内は(2)式と同様の理由からマであり、{ε,0}* = ミであるから
L(M) = ム{0}メ
これを正規表現すれば
L(M) = モ0ヤ
となる。

-----答え-----
ア=3R13
イ=?
ウ=?
エ=A^0
オ=A^0
カ=1R12
キ=1R23
ク=1R12
ケ={1}
コ={1}
サ=(0R11)*
シ=φ
ス={0}
セ=0R13
ソ={ε}*
タ={0}
チ={0}
ツ={1}
テ={0}
ト=?
ナ=?
ニ=?
ヌ=1R32
ネ=1R32
ノ=(0R11)*
ハ=φ
ヒ=0
フ=0
エ=?ホ=?マ=?ミ=?ム=?メ=?モ=?ヤ=?
途中までは解けたんですが?の箇所がわかりません・・・

よろしくお願いします。