問題タブ [pumping-lemma]

私は最近、言語が規則的でないことを示すためにポンピング補題を使用するように求められた課題を持っていましたが、残念ながら間違った答えを得ました。

非正規であることを証明する言語は次のとおりです。 L = {a ⁱ b ^j c ^k : i = j または j = k}

私が与えられたポンピング補題の定義は次のとおりです。

1. 対戦相手はmを選ぶ
2. ポンピング補題に矛盾する w を選びたいと思います。m を使用して文字列 w ∈ L を選択します。ここで |w| ≧メートル
3. 対戦相手は、制約に従って w の分解を選択します。
4. _{ポンピングされた文字列 w i} ∉ Lになるように i を選択しようとします。見つかった場合、L は正則ではありません。

この主題は、私が理解するのが非常に難しいことが証明されており、そのために完全な空気頭のように感じます。そのため、ポンピング補題を適切に適用する方法に関する詳細な説明をいただければ幸いです。

この言語の DFA と正規表現が必要です。

DFA はこれだと思いますが、得られる正規表現はこれ ((aUb)a)* であり、正しくないと思います。

通常の言語のポンピングの長さは、関連する言語のポンピングの長さとどのように関連していますか。たとえば、A :< B :< C がすべて通常の言語であり、k が B のポンピング長である場合、A と C のポンピング長について何か知っているでしょうか?

有限言語を見ると、サブ言語のポンピング長が小さい (<=) と素朴に考える人がいるかもしれません。{a,ab,abc} :< {a,ab,abc,abcd} のそれぞれのポンピング長は 4 <= 5 です。セットから要素を取り出しても、その最長の単語をさらに長くすることはできません。

一方、2 つの言語の同期積によって形成されるステート マシンを見ると、交差言語と共用体言語は同じステート マシン構造を持っていますが、交差の最終状態のセットが次の部分集合であるという点で異なります。ユニオンの最終状態のセット。より多くの最終状態を持つことで、ステート マシンを介してより短いパスを見つける可能性が高くなります。しかし、反対に、最終状態が少ないと、状態マシンに共同アクセスできない状態が含まれる可能性が高くなり、還元可能になります。