Säännöllisen kielen komplementti

Meillä on säännöllinen kieli L. Todistamme, että kielen L komplementti on jälleen säännöllinen kieli.

Mikä komplementti on

Kielen L komplementilla tarkoitetaan kaikkia sanoja, jotka eivät kuulu kieleen L. Komplementtia merkitään L^c. Eli aakkostolle Σ pätee:

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

Esimerkiksi kielen, jonka sanoissa on ainakin yksi symboli 1, komplementti olisi kieli, jonka sanoissa ei ole yhtään symbolia 1.

Menetelmä

Menetelmä on hyvin yksinkertainen. Meillä on säännöllinen kieli L ja sen hyväksyvä deterministinen täydellinen automaatti A = (Q, Σ, δ, q₀, F) (jokaisen äärellisen automaatin voi muuntaa sellaiseksi). Automaatin A', joka hyväksyy kielen L^c, rakennamme vaihtamalla lopputilat ja ei-hyväksyvät tilat keskenään: A' = (Q, Σ, δ, q₀, Q ∖ F). Siinä kaikki.

Esimerkki

Olkoon meillä tämä automaatti:

Kielen komplementin hyväksyvä automaatti näyttäisi tältä:

Lähteet

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