regular-language - 正規言語の証明

Question

この発言が間違っていることを証明しなければなりません。L1 = {ab|の場合 a∈L2, b∉L2} は正規言語で、L2 は正規言語です。

(a と b は文字列です。) (L1 と L2 のアルファベットが同じであると仮定します。)

私の仕事:
質問は次のように書き直すことができます: L2 が正則である場合、L1 は非正則です。(これが正しいことを証明する)

対比による証明: L2 が正則なら L1={ab| a∈L2, b∉L2} は非正則

この行の後に何をすべきかわかりません。それは正しいアプローチですか？誰かがこれを行う方法についてのヒントを教えてもらえますか?

Answer 1

A = "L1 = {ab| a∈L2, b∉L2} は正規言語" とします。
B = "L2 は通常の言語" とします。

問題は、A → B が偽であることを証明することです。これは A ∧ ¬B を証明することと同じです。英語では、次のように読みます。

L1 = {ab| a∈L2, b∉L2} は正規言語ですが、L2 は正規言語ではありません。

したがって、1 つの戦術は、L1 が規則的であることにつながる非規則的な L2 を見つけることです。それができれば、反例があり、元のステートメントが間違っていることが証明されます。