Κλειστότητα των κανονικών γλωσσών

Μια γλώσσα L είναι κανονική αν και μόνο αν υπάρχει αυτόματο A που αποδέχεται αυτή τη γλώσσα, δηλαδή L(A) = L. Θα αποδείξουμε ότι οι κανονικές γλώσσες είναι κλειστές ως προς τις πράξεις της ένωσης, της τομής, της παράθεσης και της κλειστότητας Kleene.

Κλειστότητα συνόλου ως προς πράξη

Λέμε ότι ένα σύνολο M είναι κλειστό ως προς την πράξη ⊗, αν ισχύει ότι

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

Παράδειγμα είναι η πράξη της πρόσθεσης στο σύνολο των φυσικών αριθμών. Το άθροισμα οποιωνδήποτε δύο φυσικών αριθμών είναι πάλι φυσικός αριθμός. Αντίθετα, το σύνολο των φυσικών αριθμών δεν είναι κλειστό ως προς την αφαίρεση, επειδή για παράδειγμα 7 − 15 = −8 και ο αριθμός −8 δεν είναι φυσικός.

Θα αποδείξουμε ως προς ποιες πράξεις είναι κλειστό το σύνολο των κανονικών γλωσσών. Όλες οι αποδείξεις θα είναι κατασκευαστικές, δηλαδή θα κατασκευάσουμε αυτόματο που αποδέχεται τη γλώσσα που προκύπτει.