Linguaggi Regolari e Linguaggi
Liberi
Linguaggi regolari
Potere espressivo degli automi
Costruzione di una grammatica equivalente a
un automa
Grammatiche regolari
Potere espressivo delle grammatiche
Programmazione
1
Linguaggi Regolari
●
●
Tutti i linguaggi che possono essere accettati da
automi a stati finiti non deterministici sono detti
Linguaggi Regolari
La definizione include linguaggi su tutti i
possibili alfabeti Σ finiti
Programmazione
2
Determinismo vs Non
determinismo
●
●
●
●
Abbiamo visto che, tramite la costruzione dei
sottoinsiemi, un qualsiasi automa non deterministico
può essere trasformato in uno deterministico
equivalente
Inoltre un automa deterministico può essere visto
come un particolare automa non deterministico
Pertanto in realtà è superfluo dire, nella definizione di
linguaggi regolari, che gli automi debbano essere non
deterministici
La classe di linguaggi accettati da automi deterministici
è uguale a quella dei linguaggi accettati da automi non
deterministici
Programmazione
3
Potere espressivo
●
●
●
In questo caso si dice che i due formalismi, gli
automi deterministici e non deterministici, hanno
lo stesso potere espressivo
Oltre a quello degli automi deterministici, anche
il formalismo delle espressioni regolari ha lo
stesso potere espressivo degli automi non
deterministici
Una costruzione per costruire un NFA a partire
da una qualsiasi espressione regolare si vedrà
nel corso di Compilatori
Programmazione
4
Linguaggi Regolari
●
La classe dei linguaggi regolari può essere
quindi specificata equivalentemente con tre tipi
diversi di formalismi:
–
–
–
●
Automi non deterministici (NFA)
Automi deterministici (DFA)
Espressioni Regolari
Questi tre formalismi hanno tutti lo stesso
potere espressivo
Programmazione
5
Potere espressivo superiore
●
●
●
●
Ma tutti i linguaggi sono regolari?
La risposta è NO
Ci sono dei linguaggi che non possono essere
specificati con NFA (o DFA o espressioni
regolari)
I linguaggi di questo tipo sono detti non regolari
Programmazione
6
Un esempio classico
●
●
●
L’esempio classico di linguaggio non regolare è
il seguente
L = { a nb n | n ≥ 0 }
È impossibile scrivere un automa o
un’espressione regolare che accetti/denoti
questo linguaggio
La dimostrazione di questo enunciato è
interessante e può essere trovata sulla
dispensa alternativa di sintassi
Programmazione
7
Limiti degli automi
●
Intuitivamente il motivo è che gli automi non
possono “contare”, cioè non possono
implementare un contatore che possa
assumere un qualsiasi valore intero (n) in
modo da accettare stringhe in cui ci sia una
corrispondenza fra il numero di certi elementi e
il numero di altri elementi
Programmazione
8
Potere espressivo delle
grammatiche
●
●
●
È facile scrivere una grammatica libera dal contesto
per il linguaggio visto:
S  aSb | ε
In effetti si ha che le grammatiche libere dal contesto
hanno un potere espressivo maggiore degli
automi/espressioni regolari
Ciò significa più precisamente che:
–
–
Ogni linguaggio regolare può essere generato con una
grammatica
Esiste almeno un linguaggio non regolare che è accettato da
una grammatica
Programmazione
9
Potere Espressivo delle
grammatiche
Universo dei linguaggi
Linguaggi generati da
grammatiche libere
L = { anbn | n ≥ 0 }
Linguaggi Regolari
Programmazione
10
Potere espressivo delle
grammatiche
●
●
Per mostrare la seconda parte basta usare il
linguaggio { anbn | n ≥ 0 }
Per la prima parte definiamo un algoritmo che,
dato un qualsiasi automa (deterministico o no),
costruisce una grammatica equivalente
Programmazione
11
Algoritmo: dagli automi alle
grammatiche
●
Input: Automa <S, Σ, s0, move, F>
●
Output: Grammatica <V, Σ, S, P> equivalente
●
Costruzione dei simboli non terminali di V e
dello stato iniziale:
–
–
Per ogni stato s di S costruiamo un simbolo non
terminale <s> in V
Poniamo <s0> come simbolo iniziale S della
grammatica
Programmazione
12
Algoritmo: dagli automi alle
grammatiche
Costruzione delle produzioni P:
● Per ogni s ∈ S e per ogni a ∈Σ:
–
–
●
Se c’è nell’automa una transizione etichettata con a
che dallo stato s va nello stato s’ allora inseriamo la
produzione <s>  a <s’> in P
Se c’è nell’automa una transizione etichettata con a
che dallo stato s va nello stato s’ e s’ ∈ F allora
inseriamo una produzione <s>  a in P
Se l'automa accetta anche la stringa vuota ε
allora bisogna fare un ulteriore passo e creare
un simbolo iniziale fittizio
Programmazione
13
Algoritmo: dagli automi alle
grammatiche
●
Se l'automa accetta la stringa vuota:
–
Aggiungere un ulteriore simbolo non terminale <s0'>
e porlo come simbolo iniziale della grammatica a
posto di <s0>
–
Inserire la produzione <s0'>  ε
–
Aggiungere una produzione <s0'>  α per ogni
produzione <s0>  α che si trova già in P (costruito
come nella pagina precedente)
Programmazione
14
Esempio
a
0
a
1
b
2
c
{a, b, c}
Programmazione
3
15
Esempio
●
Seguendo le indicazioni dell’algoritmo
otteniamo la seguente grammatica, al primo
passo
<0>  a <0> | a <1> | a
<1>  b <2>
<2>  c <3> | c
<3>  a <3> | b <3> | c <3> | a | b | c
• Ma l'automa accetta anche la stringa vuota
Dobbiamo completare come segue
• Programmazione
16
Esempio
• Nuovo simbolo iniziale <0'>
<0'>  ε | a <0> | a <1> | a
<0>  a <0> | a <1> | a
<1>  b <2>
<2>  c <3> | c
<3>  a <3> | b <3> | c <3> | a | b | c
Programmazione
17
Grammatiche regolari
●
Le grammatiche in cui le produzioni sono tutte
della forma
A  aB oppure
A  a oppure
Aε
● Sono chiamate Grammatiche Regolari e
hanno lo stesso potere espressivo degli
automi/espressioni regolari
● L’algoritmo visto genera grammatiche regolari
Programmazione
18
Linguaggi liberi
●
●
●
●
Tutti i linguaggi che possono essere specificati
attraverso una grammatica libera dal contesto
sono detti Linguaggi Liberi
I linguaggi liberi, sappiamo dal potere
espressivo, includono i linguaggi regolari più
altri linguaggi non regolari come { anbn | n ≥ 0 }
Ma i linguaggi non liberi sono tutti i possibili
linguaggi?
La risposta è ancora NO
Programmazione
19
Linguaggi non liberi
●
Esistono dei linguaggi che non possono essere
generati da nessuna grammatica libera dal
contesto, ad esempio:
L = {am bm cm | m ≥0}
●
●
Esistono infiniti linguaggi non liberi. Esistono
infiniti linguaggi non regolari, ma liberi.
Esistono gerarchie di formalismi più potenti
delle grammatiche libere dal contesto
Programmazione
20
Potere espressivo delle
grammatiche libere
Universo dei linguaggi
Linguaggi generati da
grammatiche libere
L = { anbn | n ≥ 0 }
L = {ambmcm | m ≥ 0 }
Linguaggi Regolari
Programmazione
21