regex - 1*0* と交差する通常の言語は 1n0n になります

Question

私はオートマトン理論に関する本を読んでいます。この本は、0 と 1 の数が等しい言語が 1*0* と交差すると 1n0n になるという例を示しています。ここで、n > 0 です。

私の質問は、1*0* と交差したときに 1n0n になる正規言語を見つけるにはどうすればよいかということです。それを考える方法はありますか？

更新：答えてくれてありがとう！私が見つけようとしているのは正規の言語だと思うので、1n0n のような言語は機能しません ;) 可能ですか? 何か案は？

Answer 1

注意：0と1の数が等しく無制限である言語は、正規言語ではありません。

あなたの質問に関しては、あなたが与えた2つ以外のn個の1とそれに続くn個のゼロを取得するためにいくつかの1とそれに続くいくつかのゼロに追加できる制限はこれ以上ないと思います。

条件を満たす自明な人工言語は無数にあります。A1nB0nCここで、A、B、Cは、ゼロ幅に一致する任意の式です。

Answer 2

質問を次のように考えてみて1n0mください1n0n。基本的に、n=m という制約を追加するものは何でも。

1 つの例はanbn、a!=b です。もう一つはL = { 1n0n1m0m | n!=m, n >= 0, m >= 0 }。

また、OrangeDog が指摘したように、1n0nは規則的ではなく、規則的な言語は交点の下で閉じているため、 との交点が1*0*与えられる言語1n0nは規則的ではないということになります。