Komplement af et regulært sprog

Vi har et regulært sprog L. Vi viser, at komplementet til sproget L igen er et regulært sprog.

Hvad er et komplement

Ved komplementet til sproget L forstår vi alle de ord, der ikke er i sproget L. Komplementet betegner vi L'. Dvs. for alfabetet Σ gælder:

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

For sproget af ord, der indeholder mindst ét symbol 1, ville komplementet for eksempel være sproget, der indeholder de ord, som slet ikke indeholder symbolet 1.

Fremgangsmåde

Fremgangsmåden er meget enkel. Vi har et regulært sprog L og en deterministisk total automat A = ⟨Q, Σ, δ, q₀, F⟩, som accepterer det (enhver endelig automat kan omdannes til sådan en). Automaten A', som accepterer L', konstruerer vi ved at bytte om på accepttilstande og ikke-accepterende tilstande: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Det er alt.

Eksempel

Vi ser på denne automat:

Automaten, der accepterer komplementet til sproget, ville se sådan ud:

Kilder

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