Differenza di linguaggi regolari

Siano L₁, L₂ due linguaggi regolari. Dimostreremo che anche la loro differenza L = L₁ ∖ L₂ è un linguaggio regolare.

Idea

In realtà non c’è molto da dimostrare. Per la differenza di due insiemi vale infatti la relazione

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

dove L₂′ è il complemento del linguaggio L₂. Dagli articoli sull’intersezione di linguaggi regolari e sul complemento di un linguaggio regolare sappiamo che i linguaggi regolari sono chiusi rispetto a entrambe le operazioni. Questo significa che sappiamo costruire un automa che accetta l’intersezione di linguaggi e un automa che accetta il complemento di un linguaggio. Possiamo quindi usarli per costruire un automa che accetta il linguaggio L₁ ∩ L₂′, che è proprio il linguaggio L₁ ∖ L₂.

Esempio

Consideriamo questo automa A₁, che accetta tutte le parole con un numero pari di 1:

e l’automa A₂, che accetta le parole con un numero dispari di 0:

Costruiamo l’automa che accetta la differenza di questi linguaggi. Ci serve l’automa A₂′, complemento dell’automa A₂. Basta scambiare gli stati finali e quelli non finali:

Ora non resta che costruire l’automa A che accetta l’intersezione dei linguaggi L(A₁) e L(A₂′):

Fonti

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