정규 언어 증명

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가 거짓임을 증명하는 것입니다. 이것은 ∧ ¬ B. 영어로 읽는 것과 같습니다.

L1 = {ab | a∈L2, b∉L2}는 정규 언어이지만 L2는 정규 언어가 아닙니다.

따라서 한 가지 방법은 L1이 규칙적인 비정규 L2를 찾는 것일 수 있습니다. 당신이 할 수 있다면 당신은 반대 사례를 가지고 있으며, 그래서 당신은 원래의 진술을 거짓으로 입증했습니다.