チョムスキー タイプ 2 (文脈自由言語) とチョムスキー タイプ 3 (正規言語) の違いをうまく説明できません。

誰かが平易な英語で答えてくれませんか? 階層全体を理解するのに苦労しています。

ウィキペディアでこの解決策を見つけました。j>n≥ 0 というべきではありませんか? 交点は両方の言語に共通する要素だからです。

L1={a^(n)b^(n)c^(j)| で定義される言語 L1 および L2 を考えてみましょう。n,j ≥ 0} および L2 = {a^(j)b^(n)c^(n): n,j ≥ 0}。どちらも文脈自由です。ただし、それらの共通点は言語 L = {a^(n)b^(n)c^(n)| です。n≧0}。

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

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

これは客観的な試験問題であり、2 分しか与えられていないため、証明は必要ありません。オプションはregularまたはcflまたはcslです。これに取り組む方法がわかりません。

私たちがそれを次のように書くとしたら

ここで、最初の部分を L1 と 2 番目の部分を L2 と呼び、次のように補完してみてください。

モルゴンの法則 L'= L1' INTERSECTION L2'

2〜3分しかかからないという事実を考えると、それが正しい方法でも簡単な方法でもないと思います。これに対するより良いアプローチはありますか？

L={a ⁿ b ^m c ^o | n < m < o, n natural}
ポンピング補題を使用して、次のように選択しました: z = uvwxy = a ⁿ b ⁿ⁺¹ c ⁿ⁺²
|uv|<=n and |v|>0
=> uv ² wx ² y
If vwx が a および/または b であることは問題ありません。c よりも a および/または b の方が多いでしょう。しかし、vwx に c のみが含まれている場合、それは L の要素になります。
私が理解している限り、すべての新しい単語は要素ではない必要があります。 CFL ではないことを示す L の。どうすればいいですか？

Context free Language および Deterministic Context free languages で決定できる、認識している問題を挙げていただけますか。Stack Overflow と Wiki で決定不能な問題のリストに関する情報を入手しましたが、CFG や DCFG とは詳細には関係ありません。この問題のリスト (証明/リンク付き) は、そのような問題を探している人にとって非常に役立つ可能性があります。

2 つの文脈自由言語 (L = L1 ∩ L2) の共通部分を取得する方法を理解するのに苦労しています。私は非常に一般的な例を見てきました:

しかし、次のような例はどうでしょうか。

私が持っている両方の文脈自由文法を考え出す必要があることがわかりました：

しかし、この時点では、この 2 つを交差させて言語を作成する方法がわかりません。誰かが私に方法を教えてくれるかどうか疑問に思っていました。前もって感謝します。