Reguláris nyelv komplementere

Adott egy L reguláris nyelv. Bebizonyítjuk, hogy az L nyelv komplementere is reguláris nyelv.

Mi az a komplementer

Az L nyelv komplementerén mindazokat a szavakat értjük, amelyek nincsenek az L nyelvben. A komplementert L' jelöli. Vagyis a Σ ábécére teljesül, hogy:

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

Például az olyan szavakból álló nyelv komplementere, amelyek tartalmaznak legalább egy 1 szimbólumot, az a nyelv, amely azokat a szavakat tartalmazza, amelyekben egyetlen 1 szimbólum sincs.

Eljárás

Az eljárás nagyon egyszerű. Adott az L reguláris nyelv és egy azt elfogadó A = ⟨Q, Σ, δ, q₀, F⟩ determinisztikus teljes automata (minden véges automata átalakítható ilyenné). Az L' nyelvet elfogadó A' automatát úgy szerkesztjük meg, hogy felcseréljük a végállapotokat és a nem végállapotokat: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Ez az egész.

Példa

Adott ez az automata:

A nyelv komplementerét elfogadó automata így nézne ki:

Források

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