ここに宿題の問題があります：
Is L_4 Regular?
Let L_4 = L*, where L={0^i1^i | i>=1}.
私は L が非正規であることを知っており、Kleene Star がクローズド オペレーションであることを知っているので、L_4 は非正規であると仮定します。
しかし、私の教授は上記の例を提供しました。彼は、が互いに等しいL = {0^p | p is prime}ことを証明することにより規則的であると述べました(この場合、 e は空の単語を意味します)。L*L(000* + e)
したがって、彼の方法には の正規表現を形成することが含まれていまし0^pたが、本質的に既に正規表現を持っている場合、どうすればそれを行うことができるでしょうか?
通常の言語は、Kleene スターの下で閉鎖されています。つまり、言語 R が規則的であれば、R* も規則的です。
しかし、この推論は逆方向には機能しません。P* が実際に正則である非正則言語 P があります。
あなたの質問でそのような P の 1 つに言及しました: p が素数の文字列 0^p のセットです。
P が少なくとも文脈依存であることを示すために、通常の言語と文脈自由言語のポンピング補題を使用するのは簡単です。ただし、P* は言語 0^q と同等です。ここで、q は 0 個以上の素数の合計です。しかし、これは q=0 (空の文字列) と任意の q>=2 の場合に当てはまります。そのため、P 自体は正則ではありませんが、P* は 3 状態 DFA で認識できます。
したがって、L がコンテキストフリーであることは、 L_4 = L* が規則的かどうかには関係ありません。上記の P* で行ったように、L_4 を認識する DFA を構築できれば、明らかに規則的です。機能する DFA を見つけようとしている過程で、ポンピング引数の基礎として使用できるいくつかのパターンが明らかになるでしょう。Myhill-Nerodeの定理は、言語が非正規であることを証明するための別のアプローチであり、その言語が接頭辞の分析と拡張子の識別に役立つ場合に役立ちます。言語が特定の関係の下で等価クラスの有限集合に分解できる場合、言語はその多くの状態を含む DFA で認識できます。
編集：OPの例L_4が正規であるかどうか疑問に思っている人のために...そうではありません。正規言語のポンピングレンマを使用して証明できます。
L_4 が規則的で、「ポンピング長」が P であると仮定します。L_4 の要素である文字列 w=0 P 1 Pを考えてみましょう。|y| を使用して w=xyz の形式に分解する必要があります。>= 1 かつ |xy| <= P. これらの条件を満たす xy の選択は、すべてゼロで構成されます。ただし、n != 1 の文字列 w' = xy n z は、0 と 1 の数が一致しないため、L_4 の要素にはなりません。したがって、ポンピング補題は成り立たず、L_4 は正則ではありません。