私はいくつかの方法でこの問題に取り組もうとしましたが、いくつかの場所を調べても答えがありませんでした。質問は次のとおりです。
[質問]
2 つの正規言語 (有限記述言語 idk と呼ばれる場合があります) と が与えられた場合L1、L2新しい言語を次のように定義します。
L = {w1w2| there are two words, x,y such that : xw1 is in L1, w2y is in L2}
を使用して表示することになってL is regularいますが、次の制限があります。
Equivalence クラスを使用する必要があり、他に方法はありません
Rank(L)同等クラスの数に制限を表示するように使用できません。代わりに、それらを表示する必要があります
私は完全な証明を期待しているわけではありませんが (それはありがたいです)、そのようなことを行う方法についての説明です。
前もって感謝します。
L = {w1w2 | x、yの2つの単語があり、：xw1はL1にあり、w2yはL2にあります}は、L1とL2が正規言語の場合、正規言語です。
L suff = {w 1 | xw1∈L1 } Lpref = { w 2 | _ _ w2y∈L2 } _ _ _
と、
L = L suff L pref
の有限オートマトンを構築することで簡単に証明できますL。
L1の有限オートマトン（FA）がM 1であり、L2のFAがM2であると仮定します。
[解決策]
Lの非決定性有限オートマトン（NFA）は、M 1のすべての状態からM2のすべての状態にNULL遷移（^エッジ）を導入することで描画できます。その後、NFAをDFAに変換できます。
例：
L 1 = {ab、ac}およびL 2 = {12、13}
L = {ab、ac、12、13、a12、a2、ab12、ab2、a13、a3、ab13、ab3、............}注
： w1とw2は NULLにすることができます
M1 =はQ={q 0、q 1 、 qf }とエッジで 構成されます。
q 0 --- a -----> q 1、
q 1 --- b / c ---> q f
同様に：
M2 =はQ={p 0、p 1、p f }で構成され、エッジがあります。
p 0 --- 1----> p 1、
p 1 --- 2/3 ---> p f
ここで、Mと呼ばれるLのNFAは、Q = {q 0、q 1、q f、p 0、p 1、p f }で構成されます。ここで、Mの最終状態はp fであり、エッジは次のとおりです。
q 0 --- a -----> q 1、
q 1 --- b / c ---> q f、
p 0 --- 1 -----> p 1、
p 1 --- 2/3 ---> p f、q 0 ---- ^ ----> p 0、
q 1 ---- ^ ----> p 0、
q f ---- ^ ----> p 0、q 0 ---- ^ ----> p 1、
q 1 ---- ^ ----> p 1、
q f ---- ^ ----> p 1、q 0 ---- ^ ----> p f、
q 1 ---- ^ ----> p f、
q f ---- ^ ----> p f
^NULL-Transitionを意味します。
これで、NFAは簡単にDFAに変換できます（私はあなたに任せます）
[回答]
LのDFAが可能であるため、Lは正規言語です。
DFA / NFAの数字を描くことを強くお勧めします。そうすれば、概念が明確になります。>