私の教科書によると、L1 = A* - L1 の補集合は、L1 が正規言語である限り、正規言語です。
A* には、Context Free 言語、Context Sensitive 言語、Recursively Enumerable 言語も含まれていませんか? A*-L1 にはそれらもすべて含まれますね。では、どうすれば定期的になることができますか？
有限ステート マシンの表現の下で、補語がまだ通常の言語である理由がわかりました。しかし、その背後にある理論を理解することはできません。
また、 A* - L1 = A* 交差補数(L1) . 補数によって定義されるもので補数を定義することは、トートロジーではありませんか? それがどのように有効なのか、私にはよくわかりません。
ありがとう。
あなたが混乱しているのは、「A*文脈自由言語、文脈依存言語、帰納的可算言語も含まれていませんか？」と言うときだと思います。文字列のセットである、と言語のセットであるA*、を混同しています。Powerset(A*)
Powerset(A*) - {L1}「文脈自由言語、文脈に敏感な言語、帰納的可算言語」を含むセットであることは事実ですが、実際には、正規言語L（文字列のセット）が与えられた後、その言語が与えられるという定理とは関係ありません。 A*-L、これも文字列のセットであり、正規言語でもあります。
TL; DR質問のレベル間に混乱があります：文字列のセットと言語のセット。A*intoLとinregularの2つのパーティションも、regularA*-LであるL必要がありますA*-L。 A*文字列のセットであるため、「言語を含む」ことはできません。
2番目の質問へ：
また、A * --L1 = A *交差補集合（L1）。補集合によって定義されたもので補集合を定義するのはトートロジーではありませんか？
いい質問です。これが定義として提示されているのではないかと思います。つまり、演算子を定義しているだけ-です。私の知る限り、「補完機能」を定義しているわけではありません。おそらく「補数」はすでに定義されており、あなたの本は現在、減算演算子を定義しようとしています。そうでなければ、これは定義ではなく定理です。
Hopcroft & Ullmanのコピーは見つかりませんが、ここで正規言語の補語の正しい定義を見つけたと思います。L の補数は、L のメンバーである文字列を除く任意の文字列を受け入れる DFA であると言うのは正しく、より会話的に明確に思えます。したがって、受け入れ状態をすべての (以前の) 非受け入れ状態に移動すれば完了です。補数は DFA の単なる順列であるため、結果は依然として DFA です。
表記に関する限り、補数演算子はどこにあるのL1 = A* - L1かと正しく読むべきときとして読んでいると思います。complement L1 = A* - L1complement
オートマトンの証明を理解できれば、すべてを理解できます。その背後にある直感は、オートマトンを実行して最終状態で停止するかどうかを確認することで通常の言語を認識できる場合、同じオートマトンを実行するだけで、(すべての文字列のセットにわたって) その言語の補数を認識できるということです。非最終状態で停止するかどうかを確認します。すべての文字列は何らかの状態で停止し、最終状態で停止する場合にのみ言語が規則的であるため、非最終状態で停止する場合にのみ非規則的です。それはかなり直感的だと思います。また、言語が規則的であることを自分自身に証明するために必要な唯一のことは、そのためのオートマトンを構築することです: すべての最終状態と非最終状態を交換するだけです。