Sifat ketertutupan bahasa nalar

Bahasa L ialah bahasa nalar jika dan hanya jika wujud automaton A yang menerima bahasa ini, iaitu L(A) = L. Kita akan membuktikan bahawa bahasa nalar tertutup terhadap operasi kesatuan, persilangan, perangkaian dan tutupan.

Ketertutupan set terhadap suatu operasi

Kita katakan bahawa set M tertutup terhadap operasi ⊗ jika

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

Contohnya ialah operasi penambahan pada set nombor asli. Hasil tambah mana-mana dua nombor asli ialah nombor asli juga. Sebaliknya, set nombor asli tidak tertutup terhadap penolakan kerana, misalnya, 7 − 15 = −8, dan nombor −8 bukan nombor asli.

Kita akan membuktikan terhadap operasi yang mana set bahasa nalar tertutup. Semua bukti bersifat konstruktif, iaitu kita membina automaton yang menerima bahasa yang terhasil.