Συμπλήρωμα κανονικής γλώσσας

Έστω μια κανονική γλώσσα L. Θα αποδείξουμε ότι το συμπλήρωμα της γλώσσας L είναι πάλι κανονική γλώσσα.

Τι είναι το συμπλήρωμα

Συμπλήρωμα της γλώσσας L ονομάζουμε όλες τις λέξεις που δεν ανήκουν στη γλώσσα L. Το συμπλήρωμα το συμβολίζουμε L'. Δηλαδή για το αλφάβητο Σ ισχύει ότι:

$$L^{\prime }=\{w\in {\mathrm{\Sigma }}^{\ast }|w\notin L\}.$$

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

Μέθοδος

Η μέθοδος είναι πολύ απλή. Έχουμε μια κανονική γλώσσα L και ένα ντετερμινιστικό πλήρες αυτόματο A = ⟨Q, Σ, δ, q₀, F⟩ που την αποδέχεται (κάθε πεπερασμένο αυτόματο μπορεί να μετατραπεί σε τέτοιο). Το αυτόματο A', που αποδέχεται τη γλώσσα L', το κατασκευάζουμε εναλλάσσοντας τις τελικές και τις μη τελικές καταστάσεις: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Αυτό είναι όλο.

Παράδειγμα

Έστω το εξής αυτόματο:

Το αυτόματο που αποδέχεται το συμπλήρωμα της γλώσσας θα έμοιαζε ως εξής:

Πηγές

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools