Tính đóng của ngôn ngữ chính quy

Ngôn ngữ L là chính quy khi và chỉ khi tồn tại ôtômat A đoán nhận ngôn ngữ đó, tức là L(A) = L. Ta sẽ chứng minh rằng lớp ngôn ngữ chính quy đóng đối với các phép hợp, phép giao, phép ghép và bao đóng.

Tập hợp đóng đối với một phép toán

Ta nói tập hợp M đóng đối với phép toán ⊗ nếu

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

Ví dụ là phép cộng trên tập các số tự nhiên. Tổng của hai số tự nhiên bất kì lại là một số tự nhiên. Ngược lại, tập các số tự nhiên không đóng đối với phép trừ, vì chẳng hạn 7 − 15 = −8 mà −8 không phải là số tự nhiên.

Ta sẽ xét xem lớp ngôn ngữ chính quy đóng đối với những phép toán nào. Mọi chứng minh đều mang tính xây dựng, tức là ta xây dựng một ôtômat đoán nhận ngôn ngữ thu được.