regular-language - 2 つの (不規則な) 文脈自由言語の結合は、通常の言語になりますか?

Question

L1 と L2 (不規則な) 文脈自由言語が与えられた場合 - L1 U L2 が規則的である可能性はありますか?

それが可能であることは知っていますが、それを示す例が見つかりません。何らかの支援を受けたいです。

Answer 1

2 つの CFL の結合は正則になりますか?

与えられた言語と文脈自由な (しかし正規ではない) 言語、両方の和集合が正規である可能性はありますか?L1L2L1 ∪ L2

はい可能です！

第 1 言語 L ₁を次のように仮定します。

L ₁ : { | どこ}anbmn = m

言語 L ₁は CFL ですが、レギュラーではありません。_{L 1}言語 のもう 1 つの書き方は です。これは、形式言語の教科書で見つけることができる CFL の最も巧妙な例の 1 つだと思います。anbn

また、第二言語 L ₂は次のとおりです。

L ₂ : { | どこ}anbmn ≠ m

L ₂も CFL ですが、正則ではありません。基本的にL2はL1_の補語.

_{ここで、L 1}と L ₂の結合は次のとおりです。

L: { | andの値に制限はありません}anbmnm

Language L=は is の正規言語および正規表現です。L1 ∪ L2La*b*

したがって、ヒントは補体 CFL の和集合が規則的であることです。

注:コンテキストフリー言語はユニオン操作の下で閉じられるため、2 つの CFL のユニオンは常に CFL になります (通常の言語のクラスは CFL のクラスのサブセットであるため、通常の言語にすることができます)。ただし、CSL などの非 CFL にすることはできません。 .

コメントに基づいて追加：

2 つの CFL の交点は規則的ですか?

与えられた文脈自由な（ただし正規ではない）言語、両方の共通部分が正規である可能性はありますか?L1L2L1 ∩ L2

はい可能です！

第 1 言語 L ₁を次のように仮定します。

L ₁ : { | どこ}anbmn = m

また、第二言語 L ₂は次のとおりです。

L ₂ : { | どこ}anbmn <= 3 or n ≠ m

Language L= =は有限集合であり、したがって正規集合でもあります。L1 ∩ L2{ab, aabb, aaabbb}