Reguláris nyelvek különbsége

Legyen adott két reguláris nyelv, L₁, L₂. Bebizonyítjuk, hogy a különbségük, L = L₁ ∖ L₂ is reguláris nyelv.

Ötlet

Valójában nincs sok bizonyítanivaló. Két halmaz különbségére ugyanis igaz a következő összefüggés:

$$L_1\setminus L_2=L_1\cap L_2^{\prime },$$

ahol L₂′ az L₂ nyelv komplementere. A reguláris nyelvek metszetéről szóló fejezetből és a reguláris nyelv komplementeréről szólóból tudjuk, hogy a reguláris nyelvek mindkét műveletre zártak. Ez azt jelenti, hogy meg tudunk szerkeszteni olyan automatát, amely nyelvek metszetét fogadja el, és olyat is, amely egy nyelv komplementerét. Ezekkel az automatákkal megszerkeszthetjük azt az automatát, amely az L₁ ∩ L₂′ nyelvet fogadja el, ez viszont egyben az L₁ ∖ L₂ nyelv is.

Példa

Adott ez az A₁ automata, amely elfogadja az összes olyan szót, amelyben páros számú 1 van:

és az A₂ automata, amely a páratlan számú 0-t tartalmazó szavakat fogadja el:

Megszerkesztjük azt az automatát, amely e nyelvek különbségét fogadja el. Ehhez szükségünk van az A₂′ automatára, amely az A₂ automata komplementere. Csak felcseréljük a végállapotokat és a nem végállapotokat:

Most már csak megszerkesztjük az A automatát, amely az L(A₁) és L(A₂′) nyelvek metszetét fogadja el:

Források

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