Proprietà di chiusura dei linguaggi regolari

lezione
lezione
Proprietà di chiusura dei linguaggi regolari
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Informatica teorica
Avanzamento Avanzamento: lezione completa al 75%
Lezione precedente: Minimizzazione degli stati di un automa Corso: Materia:Informatica Teorica Prossima lezione: Automa a pila

Introduzione

modifica

Dato che per definizione i linguaggi sono degli insiemi, è possibile applicare ad essi le operazioni insiemistiche (unione, intersezione, complementazione, differenza, ...). In questa lezione ci occuperemo di dimostrare che, quando le operazioni insiemistiche coinvolgono linguaggi regolari, il loro risultato sarà anch'esso un linguaggio regolare o, detto più brevemente, i linguaggi regolari sono chiusi rispetto alle operazioni insiemistiche che analizzeremo.

Prima di addentrarci nei dettagli delle dimostrazioni indagheremo il significato delle proprietà di chiusura per i linguaggi regolari, con l'obiettivo di capire quale sia il loro ruolo nell'ambito dell'informatica teorica. A questo scopo discutiamo un breve esempio: a partire dall'alfabeto   costruiamo due linguaggi regolari   e  . Gli elementi di questi insiemi sono stringhe che rappresentano numeri binari; nel caso di   sono multipli di due, nel caso di   sono multipli di 3. Per inciso, può essere un buon esercizio dimostrare che i due linguaggi sono effettivamente regolari (suggerimento: basta costruire un accettore a stati finiti in grado di riconoscerli).

L'insieme   conterrà tutti i numeri che sono sia multipli di due sia multipli di 3, ossia tutti i multipli di 6; potremo scrivere  . Possiamo interpretare questo risultato affermando che i linguaggi   e   sono stati utilizzati per creare il linguaggio  ; generalizzando questa considerazione possiamo affermare che le operazioni insiemistiche consentono di creare linguaggi regolari complessi a partire da linguaggi regolari semplici. Affinché si possa raggiungere questo obiettivo è indispensabile che il risultato delle operazioni insiemistiche sia sempre un linguaggio regolare, esattamente ciò che intendiamo dimostrare attraverso le proprietà di chiusura.

Nei seguenti paragrafi affronteremo le dimostrazioni riguardanti la chiusura delle seguenti operazioni insiemistiche:

  • complementazione: se   è un linguaggio regolare, allora anche   lo è;
  • intersezione: se   e   sono linguaggi regolari, allora anche   lo è;
  • unione: se   e   sono linguaggi regolari, allora anche   lo è;
  • differenza: se   e   sono linguaggi regolari, allora anche   lo è.

Accanto alle abituali operazioni insiemistiche i linguaggi formali sono chiusi anche rispetto alle seguenti operazioni:

  • concatenazione: se   e   sono linguaggi regolari, allora anche   lo è;
  • operatore star di Kleene: se   è un linguaggio regolare, anche   lo è;
  • riflessione: se   è un linguaggio regolare, anche   lo è.

Per dimostrare questi risultati si sfrutterà una conseguenza del teorema di Myhill - Nerode, ossia la relazione di biunivocità esistente tra linguaggi regolari ed accettori a stati finiti. Grazie a questo aspetto è possibile affermare che, dato un linguaggio regolare è possibile costruire un accettore a stati finiti che lo riconosca e viceversa.

Dunque per dimostrare che i linguaggi regolari sono chiusi rispetto ad una particolare operazione basta fornire una procedura che permetta di costruire un automa a stati finiti in grado di riconoscere il linguaggio risultante dall'operazione.

Complementazione di un linguaggio regolare

modifica

Dimostreremo che, a partire da un generico linguaggio regolare   riconosciuto da un automa a stati finiti   è possibile costruire un accettore a stati finiti   che riconosce il linguaggio  . Considerando che ogni linguaggio riconosciuto da una macchina a stati finiti è regolare, concluderemo che   è regolare.

Teorema

modifica

I linguaggi regolari sono chiusi rispetto all'operazione di complementazione.

Dimostrazione

modifica

Si consideri un alfabeto   ed un linguaggio regolare  . Esiste almeno un automa accettore a stati finiti   che riconosce il linguaggio  .

Per definizione di complementazione possiamo scrivere  , da cui deduciamo che nel linguaggio complementare sono comprese tutte le stringhe che non si trovano nel linguaggio  .

L'automa   accetterà quindi tutte le stringhe di simboli che non saranno accettate da  ; dal punto di vista della struttura dell'automa, possiamo concludere che l'insieme   degli stati finali è il complementare dell'insieme   rispetto a  :  ; l'insieme degli stati, l'alfabeto d'ingresso, la funzione di transizione e lo stato iniziale sono invece gli stessi dell'automa  .

In conclusione, l'automa   si ottiene da   sostituendo l'insieme degli stati finali con il suo complementare rispetto all'insieme degli stati. Abbiamo quindi dimostrato che esiste almeno un accettore a stati finiti in grado di riconoscere  , pertanto il linguaggio in questione è regolare.

Esempio

modifica

Consideriamo l'insieme   ed il linguaggio   costituito da tutte le stringhe di simboli che iniziano con la sequenza  . L'obiettivo è dimostrare che anche il linguaggio costituito da tutte le stringhe che non iniziano con la sequenza   è regolare. Costruiamo quindi l'accettore a stati finiti  che riconosce il linguaggio  : L'insieme degli stati di tale automa contiene quattro elementi:

  •   è lo stato iniziale;
  •   è lo stato che riconosce tutte le stringhe che iniziano con il simbolo  ;
  •   è lo stato che riconosce tutte le stringhe che iniziano con la sequenza  ;
  •   è lo stato che riconosce tutte le stringhe che non iniziano con   o che non hanno   come secondo simbolo.

La funzione di transizione è rappresentata dalla tabella sottostante.

a b
     
     
     
     

L'insieme degli stati finali sarà  .

L'immagine sottostante mostra il diagramma degli stati dell'automa appena definito.

 

In base a quanto è stato detto in precedenza è possibile costruire l'automa che riconosce il linguaggio complementare a quello dato cambiando solamente l'insieme degli stati finali. Il nuovo insieme   è definito come   e l'automa complementare sarà  .

Il diagramma degli stati per l'automa complementare è visibile nell'immagine sottostante.

 

Intersezione di linguaggi regolari

modifica

In questa sezione dimostreremo che, dati due linguaggi regolari   e  , il linguaggio   ottenuto dall'intersezione dei due linguaggi è anch'esso regolare.

Teorema

modifica

I linguaggi regolari sono chiusi rispetto all'operazione di intersezione.

Dimostrazione

modifica

Consideriamo due linguaggi regolari   e  . Per dimostrare che il linguaggio   ottenuto intersecando i due insiemi è regolare forniremo una procedura che permetterà di costruire un accettore a stati finiti per  . Si nota subito che i due linguaggi sono costruiti a partire dal medesimo alfabeto di partenza: questa scelta è stata operata in quanto la letteratura non è concorde sulle tecniche da applicare in caso gli alfabeti fossero distinti.

Visto che i linguaggi   sono regolari, ad ognuno di essi sarà associato un accettore a stati finiti: diremo che   è l'accettore che ha   come linguaggio macchina,   è l'accettore che ha   come linguaggio macchina.

A partire dai due accettori è possibile costruire un nuovo automa a stati finiti  , in modo che le stringhe riconosciute dall'accettore siano proprio quelle che appartengono al linguaggio  .

Vediamo come procedere: per definizione di intersezione, possiamo scrivere che  ; una stringa   viene quindi accettata dall'automa   quando è accettata da tutti e due gli automi di provenienza.

Un modo per rappresentare la struttura di   è il seguente:

  •  : l'insieme degli stati è costituito da coppie ordinate di stati  ;
  •   associa ad ogni coppia ordinata di stati e ad ogni simbolo d'ingresso al massimo una coppia ordinata di stati prossimi;
  •   è la coppia ordinata degli stati iniziali;
  •   è il prodotto cartesiano degli insiemi degli stati finali.

La funzione di transizione merita un chiarimento: lo stato attuale della macchina   è rappresentato da una coppia ordinata   di stati che sono gli stati attuali in cui si trovano i due accettori   e  .   associa allo stato attuale della macchina uno stato prossimo in base al simbolo d'ingresso ricevuto. Più precisamente si potrà scrivere: .

Affinché l'evoluzione dell'automa   conduca ad uno stato finale è necessario che l'esecuzione si arresti in uno stato   in cui   e contemporaneamente  . In particolare, quando uno solo dei due stati finali è di accettazione, la stringa d'ingresso si considera non accettata in quanto riconosciuta da un solo automa e non dall'altro, contraddicendo la definizione d'intersezione.

Grazie a questa procedura è stato possibile realizzare un automa a stati finiti   in grado di riconoscere il linguaggio  ; dal momento che per tale linguaggio esiste un accettore a stati finiti, possiamo concludere che   è regolare.

Il teorema è dunque dimostrato.

Esempio

modifica

Questo esempio illustrerà un'applicazione della tecnica impiegata nella dimostrazione del teorema soprastante. I linguaggi coinvolti sono costruiti a partire da un alfabeto  .

Consideriamo il linguaggio regolare   costituito da tutte le stringhe che contengono un numero pari di simboli "1". Consideriamo poi un secondo linguaggio regolare   costituito da tutte le stringhe che contengono almeno due simboli "0" consecutivi.

Possiamo affermare che il linguaggio   è costituito da tutte le stringhe che contengono un numero pari di simboli "1" e almeno due simboli "0" consecutivi; dimostreremo che tale linguaggio è regolare costruendo un automa riconoscitore attraverso la tecnica impiegata nella dimostrazione precedente.

Prima di presentare l'accettore riguardante il linguaggio   vale la pena di mostrare gli accettori dei due linguaggi   e  .

Nel caso del linguaggio costituito da stringhe con un numero pari di simboli "1", il diagramma degli stati per l'automa che lo riconosce è visibile nell'immagine sottostante.

 

Il linguaggio costituito da stringhe che contengono una sequenza di almeno due simboli "0" è associato all'accettore illustrato nel diagramma degli stati visibile di seguito.

 

Il seguente diagramma a stati è suddiviso in tre parti: in alto è visibile il diagramma a stati dell'automa che riconosce le stringhe contenenti almeno due zeri, sulla destra è visibile l'accettore che riconosce le stringhe con un numero pari di simboli "1", mentre nella zona centrale è presente il diagramma a stati dell'automa che accetta il linguaggio  , costruito seguendo il metodo proposto nella dimostrazione del teorema.

 

Abbiamo in questo modo dimostrato l'esistenza di un accettore a stati finiti che ha   come linguaggio macchina; come conseguenza il linguaggio in questione deve per forza essere regolare.

Unione di linguaggi regolari

modifica

A rigor di logica non sarebbe necessario presentare una dimostrazione per il caso dell'unione insiemistica di linguaggi regolari, in quanto è possibile formulare l'unione di due insiemi utilizzando l'intersezione e la complementazione.

Dati due linguaggi regolari   e   e considerando le leggi di De Morgan è possibile scrivere  . Applicando poi i due teoremi dimostrati in precedenza si può dedurre che i linguaggi regolari sono chiusi anche rispetto all'unione.

Nonostante ciò, dal punto di vista didattico è indubbiamente interessante provare a dimostrare il teorema riguardante l'unione di linguaggi regolari sfruttando una tecnica simile a quella presentata per l'intersezione, semplicemente adattando la definizione dell'automa prodotto alle caratteristiche dell'operazione di unione.

Teorema

modifica

I linguaggi regolari sono chiusi rispetto all'operazione di unione.

Dimostrazione

modifica

Consideriamo due linguaggi regolari   e  . Per definizione, l'unione insiemistica dei due linguaggi sarà  .

Dato che i due linguaggi sono regolari, esisteranno anche due accettori a stati finiti   e  .

Per dimostrare l'esistenza di un automa accettore in grado di riconoscere il linguaggio   procederemo in modo analogo a quanto fatto nella dimostrazione riguardante l'intersezione insiemistica, ma dovremo prestare attenzione al modo in cui definiremo gli stati finali. Infatti, mentre nel caso dell'intersezione uno stato di accettazione richiedeva che entrambi gli stati di partenza fossero di accettazione, in questo caso basterà che uno solo dei due, oppure tutti e due, siano stati finali.

Grazie a questa considerazione è possibile identificare le caratteristiche dell'automa   in grado di riconoscere il linguaggio  :

  •  ;
  •  ;
  •  
  •  .

Procedendo in modo analogo a quanto fatto nel caso del teorema riguardante l'intersezione è possibile dimostrare che l'accettore appena descritto ha come linguaggio macchina proprio  .

In conclusione, siccome   è un linguaggio formale associato ad un accettore a stati finiti, dev'essere necessariamente un linguaggio regolare.

Esempio

modifica

Presentiamo un esempio di applicazione del teorema in cui si costruirà l'accettore a stati finiti dell'unione di due linguaggi regolari definiti sull'alfabeto  . Più precisamente, il linguaggio   contiene tutte le stringhe che iniziano con la sequenza "10", mentre il linguaggio   è formato da tutte le stringhe che terminano con la sequenza "01". L'unione insiemistica dei due linguaggi, indicata con  , è un linguaggio che contiene tutte le stringhe che iniziano con la sequenza "10" oppure che finiscono con la sequenza "01". Il diagramma a stati del linguaggio   è presentato di seguito.

 

Qui sotto è visibile il diagramma a stati per il linguaggio  .

 

Applicando la tecnica di costruzione dell'automa prodotto, si ottiene un automa accettore per il linguaggio   che ha il diagramma degli stati sottostante.

 

Come si può notare osservando il diagramma, vi sono alcuni stati che non vengono visitati durante l'evoluzione dell'automa; ciò significa che l'applicazione della tecnica dell'automa prodotto non conduce, in generale, ad un automa a stati minimi. In generale, quindi, è consigliabile ridenominare gli stati e sottoporre ad ottimizzazione l'automa ottenuto mediante questo procedimento.

Differenza di linguaggi regolari

modifica

Per la dimostrazione della differenza di due linguaggi regolari non sarà necessario produrre un accettore a stati finiti, bensì verranno sfruttate le proprietà delle operazioni già esaminate per estendere la chiusura anche al caso dell'operazione di differenza.

Teorema

modifica

I linguaggi regolari sono chiusi rispetto all'operazione di differenza.

Dimostrazione

modifica

Siano dati due linguaggi formali   e  . La differenza tra i due insiemi è un linguaggio   con la seguente caratteristica:  .

Le stringhe che fanno parte del linguaggio   appartengono a   e al complementare di  ; potremo quindi scrivere  .

Dato che questa espressione contempla unicamente linguaggi regolari ed operazioni per le quali è già stata dimostrata la chiusura, possiamo concludere che il linguaggio   è regolare. È quindi dimostrato che i linguaggi regolari sono chiusi rispetto all'operazione di differenza.

Differenza simmetrica di linguaggi regolari

modifica

In modo analogo a quanto visto per la differenza di linguaggi regolari, si può dimostrare che anche la differenza simmetrica è un'operazione chiusa rispetto ai linguaggi regolari.

Teorema

modifica

I linguaggi regolari sono chiusi rispetto all'operazione di differenza simmetrica.

Dimostrazione

modifica

Siano dati due linguaggi   e  . Per definizione di differenza simmetrica possiamo scrivere  ; questa formulazione della differenza simmetrica contiene solamente linguaggi regolari ed operazioni insiemistiche per le quali è già stata dimostrata la chiusura. Ne possiamo concludere che il linguaggio   è regolare e, per la generalità di tale risultato, che il teorema è dimostrato.

Conseguenze pratiche delle proprietà di chiusura

modifica

Le tecniche impiegate durante la dimostrazione di alcune proprietà di chiusura (complementazione, unione e intersezione), meritano un approfondimento; infatti, sebbene esse siano state introdotte con l'obiettivo di offrire una dimostrazione costruttiva dei teoremi, la loro utilità pratica è di gran lunga maggiore.

Nelle dimostrazioni in questione è stato evidenziato come linguaggi dotati di caratteristiche complesse possano essere formati a partire da linguaggi più semplici; sono state inoltre presentate delle tecniche di progettazione degli accettori a stati finiti che consentono di costruire accettori complessi a partire da accettori più semplici.

Questo approccio risulta, in linea di massima, più flessibile rispetto alla costruzione di automi ad-hoc; inoltre, sfruttando gli algoritmi di minimizzazione degli stati già esaminati nella lezione precedente è facile ricondurre i nuovi accettori così progettati alle loro forme canoniche.

L'applicazione di queste tecniche permette quindi, in un sol colpo, di dimostrare la regolarità dei linguaggi e di costruire automi a stati finiti in grado di riconoscerli.

Lezione precedente: Minimizzazione degli stati di un automa Corso: Materia:Informatica Teorica Prossima lezione: Automa a pila