L1 ⊆ L2であるか確認できるアルゴリズム

質問

なんとなく分かるんですがどうやって証明すればいいのか分かりません。

Show that there exists an algorithm for determining if L1 ⊆ L2, for any regular languages L1 and L2.
すべての正規言語L1とL2に対して
L1 ⊆ L2であるか確認できるアルゴリズムが存在することを証明せよ。

L1 ⊆ L2っていうのは大きな集合L2の中に小さな集合L1がすっぽり入った図でいいんですよね?
自分なりに考えると
L2 - L1の結果が空集合ΦならL2とL1は重なっていない、
L2 - L1の結果でL2が少し欠けた(でもその欠け < L1)場合はL2とL1は部分的に重なっている。
L2 - L1の結果でL2の欠けた部分=L1ならL1 ⊆ L2
…っていうのじゃダメですよね?
もっとスマートに証明する方法を教えて下さい。

回答No.3

hpsk · ベストアンサー

#1=#2です。超長文ですがご容赦ください。

私の考え落としがなければ、#1で示した帰納法で確かに証明できます（できました）。
まじめにやろうとすると、A*とABのところの証明（特に前者）は少ししんどいですね。
とりあえず私の考えた証明の流れと、帰納法のうちA*のところだけ書いておきます。ABも同じ感じで証明できます。A|Bは簡単です。
#1ではA+も書きましたが、これは"A A*"と等価で、正規表現の定義には含まれないようなので証明には含めなくても良いでしょう。

まず、前提知識として、任意の正規表現は、それを受理する決定性有限状態オートマトン(DFA)に変換できます。逆変換も可能です。
したがって、問の命題は
「任意の正規言語L1,L2が与えられると、言語L2に含まれる記号列をを受理するDFAが、L1に含まれる記号列も受理するかどうかを判定するアルゴリズムが存在する」
と読み替えることができます。以下証明です。

---
L1を表す正規表現をR1, L2に含まれる記号列を受理するDFAをD2とする。

(1)
・R1=a（任意の記号） または R1=ε（空の記号列）のとき
任意のL2に対して、求めるアルゴリズムは明らかに存在する。
（D2が記号列a,εを受理するかを単に確かめればよい）

(2)
R1=A,R1=Bのそれぞれに対して、任意のL2について、
D2がL1に含まれる任意の記号列を受理するかどうかを判定するアルゴリズムが存在すると仮定する。

このとき、R1=A*, R1=A|B, R1=AB についても、
任意のL2(D2)について、同様の判定を行うアルゴリズムを次のように作ることができる。
(A|B, AB については省略）
・R1=A*　のとき、
以下の1-9がD2がA*を受理するかどうかを判定するアルゴリズムである。

1.D2がεを受理するかどうかを判定する。受理しなければ答はNoでアルゴリズムを終了する。

以下、D2の初期状態をs, 受理状態の集合をFとする。
また、D2の初期状態と受理状態集合のみをそれぞれt,Gと置き換えたDFAをD2(t,G)と書くことにする。（つまりD2(s,F)=D2)

2.作業用の状態集合の変数U,Cを用意する。初期値はそれぞれU={s}, C={} とする。
3.Uから1つ要素（=DFAの状態）を選ぶ。その要素をs'とする。
4.Fの全ての部分集合（F自身を含む）F1, ... ,Fk, ... , Fn について、D2(s',Fk)がAを受理するかどうかを判定する（この判定アルゴリズムは帰納法の仮定より存在する）。
5.4の判定の全てがNoなら、答はNoでアルゴリズムを終了する。
6.4の判定がYesであった部分集合 G1,..,Gnについて、G=G1∩...∩Gnを計算する。
7.Gに含まれる要素のうち、Cに含まれない要素をUに追加する。
8.Uからs'を除く。Cにs'を追加する。
9.U={} であれば、答はYesでアルゴリズム終了。そうでなければ3に戻る。

(1)(2)から、構造に関する帰納法より、任意の正規表現R1とオートマトンD2について、D2がR1の記号列を受理するかどうかを判定するアルゴリズムが存在する。
---
上記の証明の文だけではわかりにくいと思うので、説明を加えます。
D2がA*を受理するためには、
D2はεを受理し、かつ、初期状態から任意の回数のAが入力されたとき、常に受理状態でなければならないわけで、後者を示すためには、初期状態からAが入力されると受理状態にたどり着き、かつ辿り着く可能性のある受理状態からさらにAが入力されてもやはり、受理状態に辿り着く、、、の繰り返しであることをいえばいいわけです。

字だけで説明するのはかなり辛いので、わかりにくいかもしれませんが、これが一番素直な証明方法だと思います。
いろんなことを説明なしに書いてしまっているので、わかりづらい点があれば仰ってください。
また、もっとぱっと証明する方法がわかる方がいらっしゃればお願いします。

お礼

仰る通り、-は私の勘違いでした。∩が正しかったようです。
字だけの説明でもよく分かりましたよ。
hpskさんはしっかり勉強されたんですね。
私ももっと勉強します。
とても丁寧な説明、ありがとうございました!

回答No.2

hpsk

#1です。次の書き込みがかなり長文になってしまうので、分割して投稿します。

> 私なりに考えてみたのですが、
おそらく "-"（差集合）と"∩"（積集合）を混同されているのではないかと思います。
L1∩L2 = { p | p∈L1 かつ p∈L2 }
L2- L1 = { p | p∈L2 かつ (p∈L1 でない)}
ですので、ご確認ください。
ご質問の文章は、L2-L1 を L1∩L2に置き換えれば正しいです。

ただ、こういう集合論的な話だけでは証明まで持っていくのは難しいかと思います。

お礼

ありがとうございました。
詳しくは#3で。(^.^)

回答No.1

hpsk

一般に P⊂Q を示すときには、定義に戻って
p∈P ならば p∈Q
であることを示せばうまくいくことが多いです。

今回の場合、「『L1の正規表現R1が記号列sを受理するならばL2の正規表現R2も記号列sを受理する』かどうかを確認できる」ことを示せばよいように思います。

実際に完全に解いたわけではありませんが、構造に関する帰納法でうまくいくのでは？

R1=A R1=B に対するアルゴリズムがそれぞれ存在するとして、
R1=A* に対するアルゴリズムも存在する。
R1=A+ に対するアルゴリズムも存在する。
R1=(A|B) に対するアルゴリズムも存在する。
R1=AB に対するアルゴリズムも存在する。
・・・

という感じで。

お礼

ありがとうございました。
詳しくは#3で。(^.^)