Sifat ketertutupan bahasa reguler

Bahasa L reguler jika dan hanya jika ada otomaton A yang menerima bahasa tersebut, yaitu L(A) = L. Kita akan membuktikan bahwa bahasa reguler tertutup terhadap operasi gabungan, irisan, konkatenasi, dan penutup.

Ketertutupan himpunan terhadap operasi

Himpunan M dikatakan tertutup terhadap operasi ⊗ jika berlaku

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

Contohnya adalah operasi penjumlahan pada himpunan bilangan asli. Jumlah dua bilangan asli mana pun juga merupakan bilangan asli. Sebaliknya, himpunan bilangan asli tidak tertutup terhadap pengurangan, karena misalnya 7 − 15 = −8, dan bilangan −8 bukan bilangan asli.

Kita akan membuktikan operasi apa saja yang membuat himpunan bahasa reguler tertutup. Semua bukti bersifat konstruktif, artinya kita mengonstruksi otomaton yang menerima bahasa yang dihasilkan.