0

L1 が決定論的文脈自由言語であり、L2 が正規言語であるとします。L1 U L2 結果 DCFL または通常?

文脈とともにいくつかの例を挙げてください

4

2 に答える 2

3

結果の言語は DCFL でなければなりません。直感的に、DCFL の DPDA と通常の言語の DFA を取得し、2 つを並行して実行して、どちらかが受け入れられるかどうかを確認することで、文字列が DCFL と通常の言語の和集合にあるかどうかを確認できます。通常の言語が和集合の下で閉じていることを示す製品構成のバリエーションを使用して、そのプロセスをシミュレートできます。DFA 状態と DPDA 状態の組み合わせごとに 1 つの状態を持つ DPDA を構築し、遷移がシミュレートされるように構造化します。 DPDA と DFA から並行して移行します。これに必要なスタックは 1 つだけなので、構築は問題なく機能するはずです。

お役に立てれば！

于 2015-01-16T00:38:12.450 に答える