math - 連結のある正規言語

Question

通常の言語は、操作の下で閉じられます。

init(L) = ある x に対して wx が L にあるような文字列 w の集合。

編集: x は、任意の文字列、文字、または空の文字列にすることができます。どうすればそれを証明できますか?

Answer 1

OK、最初は質問を読み違えていましたが、今はわかりました。それはまだ些細なことです。自動化を見ると、検索対象は自動化の一部であり、2 つの状態セット S1 と S2 に分かれているため、それらの間の遷移は 1 つだけです (S1->S2 からの場合、S1 にはもちろん開始ノードが含まれ、S2 には終了ノードが含まれます)。ノード）。そのようなノードは常に存在します (空の言語の例外)。そのようなノードがない場合は追加できます。そのため、w は空の単語を含むセットであり、もちろん規則的です (空の言語の場合も同様です)。

Answer 2

言語を認識する有限状態オートマトンがある場合、その言語は規則的です。したがって、L が正規言語であると仮定し、A をそれを認識するオートマトンとします。ここで、A の状態が「良好」であるとします。これは、そこから開始して「受け入れ」状態で終了する可能性のある一連の遷移がある場合です。「良い」状態へのすべての遷移が受け入れ状態への直接遷移に置き換えられる、新しいオートマトン A' を定義します。この場合、A' によって認識される言語は正確に init(L) です。

Answer 3

Aの最終状態に到達できるA（元のDFA）の状態をすべてBの最終状態にする新しいDFA Bだと思います。

Answer 4

私が誤解していない限り、答えはあなたができないということです。それは真実ではないからです。

まず、言語L = {aa, bb, cc}とアルファベットを考えてみましょう{a, b, c}

だから、init(L) = {a, b, c}。ただし、 の各要素は にinit(L)ありませんL。

編集:空の文字を連結している場合、init(L) = {a, b, c, aa, bb, cc}. これはまだ と等しくありませんL。