Komplement till ett reguljärt språk

Vi har ett reguljärt språk L. Vi bevisar att komplementet till språket L också är ett reguljärt språk.

Vad är ett komplement

Med komplementet till språket L menar vi alla ord som inte finns i språket L. Komplementet betecknas L'. Det vill säga, för alfabetet Σ gäller att:

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

För språket av ord som innehåller minst en symbol 1 är till exempel komplementet det språk som innehåller de ord som inte innehåller någon symbol 1 alls.

Metod

Metoden är mycket enkel. Vi har ett reguljärt språk L och en deterministisk total automat A = ⟨Q, Σ, δ, q₀, F⟩ som accepterar det (varje ändlig automat kan omvandlas till en sådan). Automaten A' som accepterar L' konstruerar vi genom att byta plats på sluttillstånden och de icke-accepterande tillstånden: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Det är allt.

Exempel

Låt oss ta den här automaten:

Automaten som accepterar komplementet till språket skulle se ut så här:

Källor

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