Complement van een reguliere taal
We hebben een reguliere taal L. We bewijzen dat het complement van de taal L weer een reguliere taal is.
Wat is het complement
Met het complement van een taal L bedoelen we alle woorden die niet in de taal L zitten. Het complement noteren we als Lc. Voor een alfabet Σ geldt dus:
Bij de taal van woorden die minstens één symbool 1 bevatten, is het complement bijvoorbeeld de taal die de woorden bevat die geen enkel symbool 1 bevatten.
Werkwijze
De werkwijze is heel eenvoudig. We hebben een reguliere taal L en een deterministische totale automaat A = ⟨Q, Σ, δ, q0, F⟩ die haar accepteert (elke eindige automaat kan naar zo'n automaat worden omgezet). De automaat A' die Lc accepteert, construeren we door de eindtoestanden en de niet-eindtoestanden om te wisselen: A' = ⟨Q, Σ, δ, q0, Q ∖ F⟩. Dat is alles.
Voorbeeld
Neem deze automaat:
De automaat die het complement van de taal accepteert, zou er zo uitzien:
Bronnen
Hoofdstukken: Afgeslotenheid van reguliere talen, Vereniging van reguliere talen, Doorsnede van reguliere talen, Verschil van reguliere talen, Complement van een reguliere taal, Concatenatie van reguliere talen, Afsluiting van een reguliere taal
