Komplementet til et regulært språk

Vi har et regulært språk L. Vi skal bevise at komplementet til språket L igjen er et regulært språk.

Hva komplementet er

Med komplementet til språket L mener vi alle ord som ikke er i språket L. Komplementet betegner vi L'. For alfabetet Σ gjelder altså at:

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

For språket av ord som inneholder minst ett symbol 1, ville komplementet for eksempel være språket som inneholder ordene som ikke inneholder noe symbol 1 i det hele tatt.

Framgangsmåte

Framgangsmåten er veldig enkel. Vi har et regulært språk L og en deterministisk total automat A = ⟨Q, Σ, δ, q₀, F⟩ som aksepterer det (hver endelig automat kan omformes til en slik). Automaten A' som aksepterer L', konstruerer vi ved å bytte om sluttilstandene og tilstandene som ikke er sluttilstander: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Det er alt.

Eksempel

La oss ha denne automaten:

Automaten som aksepterer komplementet til språket, ville sett slik ut:

Kilder

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