정규 언어의 닫힘 성질

언어 L이 정규 언어일 필요충분조건은 이 언어를 인식하는 오토마타 A, 즉 L(A) = L인 오토마타가 존재하는 것이다. 정규 언어가 합집합, 교집합, 연접, 클레이니 폐포 연산에 대해 닫혀 있음을 증명해 보자.

연산에 대해 닫힌 집합

다음이 성립하면 집합 M은 연산 ⊗에 대해 닫혀 있다고 한다.

$$\mathrm{\forall }x,y\in M:x\otimes y\in M$$

예를 들어 자연수의 집합에서 덧셈 연산이 그렇다. 임의의 두 자연수의 합은 다시 자연수이다. 반대로 자연수의 집합은 뺄셈에 대해 닫혀 있지 않다. 예를 들어 7 − 15 = −8인데 수 −8은 자연수가 아니다.

정규 언어의 집합이 어떤 연산에 대해 닫혀 있는지 증명해 보자. 모든 증명은 구성적이다. 즉 결과로 나오는 언어를 인식하는 오토마타를 직접 만든다.