Verschil van reguliere talen

Neem twee reguliere talen L₁, L₂. We bewijzen dat hun verschil L = L₁ ∖ L₂ ook een reguliere taal is.

Idee

Eigenlijk valt er niet veel te bewijzen. Voor het verschil van twee verzamelingen geldt namelijk de volgende betrekking:

$L_{1} ∖ L_{2} = L_{1} \cap L_{2}^{c},$

waarbij $L_{2}^{c}$ het complement van de taal L₂ is. Uit de hoofdstukken over de doorsnede van reguliere talen en het complement van een reguliere taal weten we dat reguliere talen onder beide bewerkingen afgesloten zijn. Dat betekent dat we een automaat kunnen construeren die de doorsnede van talen accepteert en een automaat voor het complement van een taal. Die automaten kunnen we dus gebruiken om een automaat te construeren die de taal $L_{1} \cap L_{2}^{c}$ accepteert, en dat is tegelijk de taal L₁ ∖ L₂.

Voorbeeld

Neem deze automaat A₁, die alle woorden accepteert die een even aantal enen bevatten:

en automaat A₂, die woorden accepteert die een oneven aantal nullen bevatten:

We construeren een automaat die het verschil van deze talen accepteert. We hebben dus een automaat A₂′ nodig die het complement van automaat A₂ is. We wisselen gewoon de eindtoestanden en de niet-eindtoestanden om:

Nu hoeven we alleen nog de automaat A te construeren die de doorsnede van de talen L(A₁) en L(A₂′) accepteert:

Bronnen

Hoofdstukken: Afgeslotenheid van reguliere talen, Vereniging van reguliere talen, Doorsnede van reguliere talen, Verschil van reguliere talen, Complement van een reguliere taal, Concatenatie van reguliere talen, Afsluiting van een reguliere taal

« Vorige: Doorsnede van reguliere talen

Volgende: Complement van een reguliere taal »