linguaggi regolari - automi, espressioni regolari, grammatiche...
TRANSCRIPT
-
Linguaggi Regolariautomi, espressioni regolari, grammatiche lineari destre
Nicola FanizziCorso di Linguaggi di ProgrammazioneDipartimento di InformaticaUniversità degli Studi di Bari17 marzo 2014
-
Sommario
1 Automi a Stati FinitiAutomi DeterministiciRappresentazione di DFAConfigurazioni e TransizioniFunzione di transizione perstringheClasse dei Linguaggi a StatiFinitiAutomiNon-deterministiciLinguaggio accettato da NFAClasse dei LinguaggiNon-deterministiciEquivalenza tra DFA eNFAEsercizi
2 Espressioni RegolariDefinizioniCorrispondenzaLinguaggi/EspressioniRegolariProprietà delleEspressioni RegolariEsercizi3 Teorema di Kleene
L3 ⊆ LdfLdf ⊆ L3Ldf ⊆ LregLreg ⊆ L3L3 ⊆ LregEsercizi
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 2 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati FinitiAutomi a Stati Finiti I
qq00●
qq11 qq22 qq33 qq44 qq55
aa bb aa aa bb aa aa bb aa aa bb aa
ControlControlUnitUnit
schema di automa a stati finiti
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 3 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati FinitiAutomi a Stati Finiti II
Definizione (Automa deterministico)Dato un alfabeto Σ, un automa a stati finiti deterministico (DFA)è una n-plaM = (Σ,Q, δ, q0, F)
Σ è l’alfabeto d’ingressoQ è un insieme finito e non vuoto di statiδ è la funzione di transizione:
δ : Q× Σ −→ Q
q0 è lo stato inizialeF ⊆ Q è l’insieme degli stati finali o d’accettazione
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 4 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi DeterministiciRappresentazione I
Un DFAM = (Σ,Q, δ, q0, F) è rappresentabile mediante:. un grafo detto diagramma di transizione in cui:
uno stato q ∈ Q è rappresentato da un cerchio con etichetta qlo stato iniziale q0 ha un arco entrante liberoogni stato finale viene denotato da un cerchio doppioper ogni q ∈ Q ed ogni a ∈ Σ, se ∃q′ = δ(q, a)allora si descrive un arco da q in q′ etichettato con a
q0 q q′aa′
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 5 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi DeterministiciRappresentazione II. una matrice tavola di transizione con:
sulle righegli stati qi ∈ Q, i = 1, . . . ,msulle colonnei simboli dell’alfabeto d’ingresso aj ∈ Σ, j = 1, . . . ,nin ogni casella: qji = δ(qi,aj)
δ a1 a2 · · · an→ q0 q10 q20 · · · qn0∗q1 q11 q21 · · · qn1... ... ... . . . ...qm q1m q2m · · · qnm
Nota→ stato iniziale; ∗ stati finaliN. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 6 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi DeterministiciRappresentazione III
q0 q1 q201 0
1 0,1
M = ({0, 1}, {q0, q1, q2}, δ, q0, {q2})
δ 0 1→ q0 q1 q0q1 q1 q2∗q2 q2 q2
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 7 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi DeterministiciRappresentazione IV
Osservazione δ potrebbe essere una funzione parziale:i.e. indefinita per qualche coppia (q,a)
Per ottenere una funzione δ totale si considera uno statoaggiuntivo (stato pozzo qP 6∈ F)nel quale far confluire le transizioni mancanti edal quale non si possano raggiungere stati finali
M = (Σ,Q, δ, q0, F) trasformato inMt = (Σ,Q ∪ {qp}, δt, q0, F)con δt : Q ∪ {qp} × Σ→ Q ∪ {qp} totale equivalente:∀(q, a) ∈ Q ∪ {qp} × Σ
δt(q, a) ={q′ ∃q′ = δ(q, a) ∈ Qqp altrimenti
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 8 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi DeterministiciConfigurazioni e TransizioniDatoM = (Σ,Q, δ, q0, F)una configurazione diM è una coppia
(q, x) ∈ Q× Σ∗
(stato corrente, stringa da leggere)(q, x) è detta:
iniziale se q = q0;finale se x = �;accettante se x = � e q ∈ F
δ associa ad ogni configurazione la successiva:si definisce una (relazione di) transizione tra configurazioni diM:
(q, x) `M (q′, y) sse ∃a ∈ Σ: x = ay ∧ δ(q, a) = q′N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 9 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi DeterministiciFunzione di transizione estesa
La funzione di transizione estesa1 generalizza δ avendo iningresso uno stato ed una stringa su ΣDefinizione (funzione di transizione estesa)Dato un automa a stati finitiM = (Σ,Q, δ, q0, F)Si definisce per induzione la funzione di transizione estesa
δ̂ : Q× Σ∗ −→ Q
∀q ∈ Q, ∀w ∈ Σ∗ :
δ̂(q,w) ={q sew = �δ(δ̂(q, z), a) sew = za
1Altrove indicata anche con δ∗ o δ̄ [Linz(2012), Hopcroft et al.,(2009)].N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 10 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi DeterministiciLinguaggi accettati da DFA
Una parolaw ∈ Σ∗ si dice accettata (o riconosciuta) daM se,partendo da q0,M porta ad uno stato q finaleδ̂(q0,w) = q ∈ F
ossia, dalla config. iniziale ad una di accettazione:(q0,w)
∗`M (q, �) ∧ q ∈ F
Il linguaggio accettato2 (o riconosciuto) daM è dato da:L(M) = {w ∈ Σ∗ | δ̂(q0,w) ∈ F}
Due DFAM1 eM2 si dicono equivalenti quando:L(M1) = L(M2)
2denotato spesso anche con T(·)N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 11 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi DeterministiciEsempioDFA che riconosce parole con un numero pari di a o di b
q0 q1
q2 q3
a
ba
bba
b
aaab è accettata: δ̂(q0, aab) = δ(δ̂(q0, aa), b) =δ(δ(δ̂(q0, a), a), b) = δ(δ(δ(δ̂(q0, �), a), a), b) =δ(δ(δ(q0, a), a), b) = δ(δ(q1, a), b) = δ(q0, b) = q2 ∈ Fovvero: (q0, aab) ` (q1, ab) ` (q0, b) ` (q2, �)
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 12 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi DeterministiciClasse dei Linguaggi a Stati Finiti
Definizione (linguaggio a stati finiti deterministico)Un linguaggio L su un alfabeto Σ è un linguaggio a stati finitideterministico sse esiste un automa deterministicoM,con alfabeto di ingresso Σ, tale che L = L(M)Risulta così definita la
Classe dei Linguaggi a Stati Finiti deterministici:Ldf = {L ∈ ℘(Σ∗) | ∃M L = L(M)}
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 13 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi DeterministiciEsempi I
L(M) = {u01v | u, v ∈ {0, 1}∗}
q0 q1 q201 0
1 0,1
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 14 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi DeterministiciEsempi II
Σ ={0,1,2,3,4,5,6,7,8,9}M = (Σ,Q, δ, q0, F) ∈ DFAQ = {q0, q1, q2}
q0: classe resto 0q1: classe resto 1q2: classe resto 2
F = {q0}
q0start
q1 q2
0,3,6,9
1,4,7
2,5,8
0,3,6,9
1,4,7
2,5,80,3,6,9
1,4,7
2,5,8
δ̂(q0, 1234) = q1 6∈ F 1234 = 3× 137+ 1δ̂(q0, 7290) = q0 ∈ F 7290 = 3× 810+ 0
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 15 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi Non-deterministiciAutomi Non-deterministici
Definizione (automa non-deterministico)Un automa a stati finiti non-deterministico (NFA) è una tuplaM = (Σ,Q, δ, q0, F)dove:
Σ alfabeto di ingressoQ è un insieme finito e non vuoto di statiq0 è lo stato inizialeF ⊆ Q è l’insieme degli stati finali o d’accettazioneδ è la funzione di transizione
δ : Q× Σ −→ ℘(Q)
Per ogni (q,a) si ha un insieme di stati in cui è possibile transitareN. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 16 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi Non-deterministiciEsempio NFA
q0 q1
q2
q3
a,bb
aa,b
a
δ a b→ q0 {q0} {q0, q1}q1 {q2, q3} {q3}q2 {q3} ∅∗q3 ∅ ∅
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 17 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi Non-deterministiciFunzione di transizione estesa per NFA
Nel corso della computazione non-deterministica per ogni simbololetto, l’automa assume un insieme di stati attuali e transita, adogni nuovo simbolo, da un insieme di stati ad un insieme di statiLa funzione δ̂ estesa alle stringhe si definisce:
δ̂ : Q× Σ∗ → ℘(Q)
∀(q,w) ∈ Q× Σ∗ :
δ̂(q,w) =
{q} sew = �⋃
q̂∈δ̂(q,z)
δ(q̂,a) sew = za, a ∈ Σ
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 18 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi Non-deterministiciNFA – Accettazione di stringhe I
Una stringa si dice accettata (o riconosciuta) dal NFAM se,partendo da q0 con una stringa in ingressow,M raggiunge uno stato finale in almeno un cammino
δ̂(q0,w) ∩ F 6= ∅
ovvero (computazione non-deterministica)({q0},w)
∗` (Q̄, �) ∧ Q̄ ∩ F 6= ∅
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 19 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi Non-deterministiciNFA – Accettazione di stringhe II
Esempioq0 q1 q2 q3
a,bb a
a,ba
w = bba ∈ L(M) ?({q0}, bba) ` ({q0, q1}, ba) ` ({q0, q1, q3}, a) ` ({q0, q2, q3}, �)e {q0, q2, q3} ∩ F = {q3} 6= ∅ quindiM accettaw
(q0, bba)(q1, ba) (q3, a) bloccato
(q0, ba)(q0, a) (q0, �) NO
(q1, a)(q3, �) OK
(q2, �) NO
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 20 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Automi Non-deterministiciLinguaggi Non-deterministici
Il linguaggio accettato (o riconosciuto) daM è dato da:L(M) = {w ∈ Σ∗ | δ̂(q0,w) ∩ F 6= ∅}
Due NFA sono equivalenti se accettano lo stesso linguaggioRisulta così definita la
Classe dei linguaggi a stati finiti non deterministici:Lnf = {L ∈ ℘(Σ∗) | ∃M ∈ NFA : L = L(M)}
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 21 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Equivalenza tra DFA e NFAEquivalenza tra DFA e NFA I
Teorema (Equivalenza)Le classi di linguaggi Ldf e Lnf coincidono
Dim.
Ldf ≡ Lnf ⇔ Ldf ⊆ Lnf ∧ Lnf ⊆ Ldf
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 22 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Equivalenza tra DFA e NFAEquivalenza tra DFA e NFA II
Tesi Ldf ⊆ LnfSi consideri un DFAM = (Σ,Q1, δ, q0, F)quindi L(M) ∈ LdfDefiniamo l’NFAM′ = (Σ,Q, δ′, q0, F), dove:
δ′ : Q× Σ −→ ℘(Q)
∀(q, a) ∈ Q× Σ δ′(q, a)={δ(q, a)}Per induzione sulla lunghezza delle parole si dimostra facilmenteche: L(M′) = L(M)
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 23 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Equivalenza tra DFA e NFAEquivalenza tra DFA e NFA IIITesi Lnf ⊆ LdfSiaMN = (Σ,QN , δN , qN0 , FN) un NFAAlgoritmo di costruzione dell’DFA equivalenteMD = (Σ,QD, δD, qD0 , FD):1 QD = ℘(QN)2 qD0 = {qN0 }3 FD = {Q′ ⊆ QN | Q′ ∩ FN 6= ∅}4 δD : QD × Σ −→ QD
∀Q′ = {q1, q2, . . . , qk} ∈ QD ∀a ∈ ΣδD(Q′, a) = δD({q1, q2, . . . , qk}, a) =
=
k⋃j=1
δN(qj, a) = ⋃q∈Q′
δN(q, a) (1)
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 24 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Equivalenza tra DFA e NFAEquivalenza tra DFA e NFA IVDim. Per L(MN) = L(MD) si dimostra che∀w δ̂D(qD0 ,w) = δ̂N(qN0 ,w) per induzione su |w|base w = �. Allora δ̂D(qD0 , �) = qD0 = {qN0 } = δ̂N(qN0 , �)passo w = va.Ipotesi di induzione: δ̂D(qD0 , v) = δ̂N(qN0 , v) (H)
δ̂D(qD0 ,w) = δ̂D(qD0 , va) =def. δ̂D
= δD(δ̂D(qD0 , v), a) =(H)= δD(δ̂N(qN0 , v), a) =(1)=
⋃q∈δ̂N(qN0 ,v)
δN(q, a) =def. δ̂N
= δ̂N(qN0 , va) = δ̂N(qN0 ,w)N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 25 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Equivalenza tra DFA e NFATrasformazione NFA→ DFA I
Nel caso peggiore: 2|QN | stati necessariEsempioLn = {w ∈ {0, 1}∗ | w ha n-esimo bit dalla fine acceso}
q0 q1 q2 · · · qn−1 qn
0,11 0,1 0,1 0,1 0,1
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 26 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Equivalenza tra DFA e NFATrasformazione NFA→ DFA IINella pratica1QD := {q0};2 elaborato[{q0}] := false;3 while ∃Q ∈ QD : ¬elaborato[Q] do4 begin { lavora su Q }5 for each a ∈ Σ6 begin7 Qa := ∪q∈Q δN(q, a);8 if Qa /∈ QD then9 begin10 QD := QD ∪ {Qa};11 elaborato[Qa] := false12 end13 δD(Q, a) := Qa14 end15 elaborato[Q] := true16 endN. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 27 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Equivalenza tra DFA e NFAEsempio Trasformazione NFA→ DFA
q0 q1
q2
q3
a,bb
aa,b
a
{q0} {q0, q1}
a
b
{q0, q2, q3}
{q0, q1, q3}
a
b
{q0, q3}a
b a ba
b
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 28 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti EserciziEsercizi I
1 Costruire un DFA che accetti il linguaggio:L = {w ∈ {a, b}∗ | w ha un numero pari di b e dispari di a}
2 Costruire un DFA che accetti il linguaggio:L = {w ∈ {a, b}∗ | w 6= uaav, u, v ∈ {a, b}∗}
3 Trasformare in DFA questo NFA:
q0 q1
0,10 1
1
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 29 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti EserciziEsercizi II
4 Determinare L(M) e trasformare in DFA questo NFA:
q0 q1 q2ba,b
a5 determinare un automa per i seguenti linguaggi:
ling. L1 su {a, b} delle stringhe che finiscono con aa:w ∈ L1 ssew = zaa, con z ∈ {a, b}∗ling. L2 su {0, 1} delle stringhe con tre 0 consecutivi:w ∈ L2 ssew = u000v, con u, v ∈ {0, 1}∗ling. su {0, 1} delle stringhe con 011 come sottostringaling. L4 su {a, b} delle stringhe che cominciano o finiscono conab:w ∈ L4 ssew = aby ∨w = yab, con y ∈ {a, b}∗
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 30 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Esercizi
Esercizio 1. Costruire un DFA che accetti il linguaggio:L = {w ∈ {a, b}∗ | w ha un numero dispari di a e pari di b}Soluzione: SiaM = (Σ,Q, δ, q0, F) ∈ DFA
Q = {q0, q1, q2, q3} doveq0 stato per un numero pari di a e di bq1 stato per un numero dispari di a e pari di bq2 stato per un numero pari di a e dispari di bq3 stato per un numero dispari di a e di bfunzione di transizione δ definita:δ(q0, a) = δ(q3, b) = q1δ(q0, b) = δ(q3, a) = q2δ(q1, a) = δ(q2, b) = q0δ(q1, b) = δ(q2, a) = q3
q0 stato inizialeF = {q1}
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 31 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Esercizi
q0 q1
q2 q3
a
ba
bba
b
a
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 32 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Esercizi
Esercizio 2. Costruire un DFA che accetti questo linguaggio:L = {w ∈ {a, b}∗ | w 6= uaav, u, v ∈ {a, b}∗}Soluzione: SiaM = (Σ,Q, δ, q0, F) ∈ DFA
Q = {q0, q1, q2} doveq0 stato per parole non contenenti due o più a consecutive eterminanti con bq1 stato per parole non contenenti due o più a consecutive eterminanti con aq2 stato pozzo per parole contenenti due o più a consecutive
q0 stato inizialeF = {q0, q1}
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 33 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Esercizi
funzione di transizione δ definita:δ a b
→ ∗q0 q1 q0∗q1 q2 q0q2 q2 q2
q0 q1 q2
ab
ba a.b
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 34 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Esercizi
Esercizio 3. Trasformare in DFA questo NFA:
q0 q1
0,10 1
1Soluzione: SiaM′ = (Σ,Q′, δ′, q′0, F′) ∈ DFA
Q′ = {∅, {q0}, {q1},Q}{q0} stato inizialeF′ = {{q1},Q}funzione di transizione δ′ definita:
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 35 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Automi a Stati Finiti Esercizi
{q0} {q1} Q ∅1
0
01
0,1
0,1
∅ stato pozzo per definire δ′ totale
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 36 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Espressioni Regolari DefinizioniLinguaggi Regolari
Definizione (linguaggio regolare)Dato un alfabeto finito Σun linguaggio L su Σ è un linguaggio regolare sse:
L è finitooppureL può essere ottenuto induttivamente mediante leoperazioni:1 L = L1 ∪ L2 con L1,L2 regolari2 L = L1 · L2 con L1,L2 regolari3 L = L∗1 con L1 regolare
Definiamo l’insieme di tali linguaggi, denotato con Lreg,la classe dei linguaggi regolariOsservazione ∅ ∈ Lreg e {�} ∈ Lreg
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 37 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Espressioni Regolari DefinizioniEspressioni Regolari
Definizione (espressione regolare)Dato un alfabeto finito Σ, una stringa R sull’alfabeto ampliatoΣ ∪ {�,+, ∗, ·, ∅, (, )} è una espressione regolare (ER) di alfabetoΣ sse vale una delle seguenti condizioni:
R = ∅R = �R = a con a ∈ ΣR = (R1+R2) con R1,R2 espressioni regolari di alfabeto ΣR = (R1 · R2) con R1,R2 espressioni regolari di alfabeto ΣR = (R1)∗ con R1 espressione regolare di alfabeto Σ
L’insieme delle espressioni regolari di alfabeto Σverrà denotato conRΣ o semplicementeRN. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 38 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Espressioni Regolari Corrispondenza Linguaggi/Espressioni RegolariLinguaggi ed Espressioni RegolariAd ogni espr. regolare R corrisponde un ling. regolare L(R):
espressione regolare linguaggio regolare∅ ∅� {�}a {a}
(R1 + R2) L(R1) ∪ L(R2)(R1 · R2) L(R1) · L(R2)
(R)∗ (L(R))∗
Risulta così definita la funzione3 L : R −→ ℘(Σ∗).Osservazioni
� non strettamente necessaria perché {�} = L(∅∗)Data l’associatività e assumendo che ∗ preceda · e questopreceda+ , si possono eliminare le parentesi
3Denotata, su alcuni testi, anche con SN. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 39 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Espressioni Regolari Corrispondenza Linguaggi/Espressioni RegolariProprietà
ProposizioneUn linguaggio su Σ è regolare sse esso corrisponde ad unaespressione regolare di alfabeto ΣSi definisce la classe dei linguaggi regolari
Lreg = {L ∈ ℘(Σ∗) | ∃R ∈ R : L = L(R)}
OsservazioniUn linguaggio regolare può essere descritto da più di unaespressione:la funzione L non è iniettivaDue espressioni regolari R1 e R2 si dicono equivalenti,e si scrive R1 = R2, sse
L(R1) = L(R2)N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 40 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Espressioni Regolari Corrispondenza Linguaggi/Espressioni Regolari
Esempidata R = (a∗(a + b)):L(R) = L(a∗(a + b)) = L(a∗) · L(a + b) =(L(a))∗ · (L(a) ∪ L(b)) = {�, a, aa, aaa, . . .} · {a, b} ={a, aa, aaa, aaaa, . . . , b, ab, aab, aaab, . . .}espressione regolare per il ling. delle stringhe d’ognilunghezza su Σ = {0, 1} con 0 e 1 alternati (in qualsiasiordine):
R = (01)∗ + (10)∗ + 0(10)∗ + 1(01)∗
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 41 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Espressioni Regolari Corrispondenza Linguaggi/Espressioni Regolari
espressione regolare per L = {a2ib2j+1 | i ≥ 0 ∧ j ≥ 0}:R1 = (aa)∗b(bb)∗Ma considerando anche R2 = (aa)∗(bb)∗b si ha
L(R1) = L(R2) = L
espressione regolare perL = {w ∈ {0, 1} | w non ha coppie di 0 consecutivi}Si osservi che
dopo uno 0 può seguire solo un 1le sottostringhe possono essere precedute o seguite da unnumero di 1 arbitrario:si possono denotare con: (1∗011∗)∗la stringhe possono essere composte di soli 1la stringhe possono terminare anche con uno 0
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 42 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Espressioni Regolari Corrispondenza Linguaggi/Espressioni Regolari
Una soluzione è R = (1∗011∗)∗(0 + �) + 1∗(0 + �)Oppure, osservando che le stringhe
si ottengono concatenando 1 o 01terminano eventualmente anche con uno 0si ottiene R′ = (1 + 01)∗(�+ 0) che è equivalente
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 43 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Espressioni Regolari Proprietà delle Espressioni RegolariProprietà dei Linguaggi Regolari I
1. (R1 + R2) + R3 = R1 + (R2 + R3) prop. associativa di+2. R1 + R2 = R2 + R1 prop. commutativa di+3. R+ ∅ = ∅+ R = R ∅ elem. neutro per+4. R+ R = R prop. di idempotenza5. (R1 · R2) · R3 = R1 · (R2 · R3) prop. associativa di ·6. R1 · R2 6= R2 · R1 non commutatività di ·7. R · � = � · R = R � elem. neutro per ·8. R · ∅ = ∅ · R = ∅ ∅ elem. assorbente per ·9. R1 · (R2 + R3) = (R1 · R2) + (R1 · R3) prop. distributiva di · risp. a+10. (R1 + R2) · R3 = (R1 · R3) + (R2 · R3) prop. distributiva di · risp. a+
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 44 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Espressioni Regolari Proprietà delle Espressioni RegolariProprietà dei Linguaggi Regolari II
11. (R)∗ = (R)∗ · (R)∗ = ((R)∗)∗ = (�+ R)∗12. (∅)∗ = (�)∗ = �13. (R)∗ = �+ R+ . . .+ Rn + (Rn+1 · R∗)14. (R1 + R2)∗ = (R∗1 + R∗2)∗ = (R∗1 · R∗2)∗ =
= (R∗1 · R∗2)∗ · R∗1 = R∗1 · (R∗1 · R∗2)∗15. (R1 + R2)∗ 6= R∗1 + R∗2 in generale16. R · R∗ = R∗ · R17. R1 · (R2 · R1)∗ = (R1 · R2)∗ · R118. (R∗1 · R2)∗ = �+ (R1 + R2)∗ · R219. (R1 · R∗2)∗ = �+ R1 · (R1 + R2)∗20. R1 = R2 · R1 + R3 sse R1 = R∗2 · R3 con R2 6= �R1 = R1 · R2 + R3 sse R1 = R3 · R∗2
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 45 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Espressioni Regolari EserciziEsercizi – Espressioni regolari
1 Quali linguaggi sono denotati da (∅∗)∗ e a∅ ?2 Elencare le stringhe di L ((a + b)∗b(a + ab)∗) di lunghezzaminore di 63 Scrivere un’espressione regolare per i seguenti linguaggia) L = {uwu ∈ {a, b}∗ | |u| = 2}b) L = {w01 | w ∈ {0, 1}∗}c) L = {z 6= wab | z,w ∈ {a, b}∗}d) delle stringhe su {a, b, c} tali che contengano almeno una a edalmeno una b;e) delle stringhe binarie che abbiano come quinto simbolo dadestra un 1f) delle stringhe binarie con al più una coppia di 1 consecutivig) delle stringhe su {a, b} che contengano un numero di adivisibile per 3
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 46 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di KleeneTeorema di Kleene
Teorema (Kleene)Vale l’equivalenza:
L3 ≡ Ldf ≡ Lreg
Dim. [schema]Tesi da provare1 L3 ⊆ Ldf (ed anche Ldf ⊆ L3)2 Ldf ⊆ Lreg3 Lreg ⊆ L3 (ed anche L3 ⊆ Lreg)
come pronunciare ”Kleene”: Kleene pronounced his last name: /’kleini/ as in ”clay-knee”. /’kli:ni/ and /’kli:n/are common mispronunciations. (His son, Ken Kleene, wrote: ”As far as I am aware this pronunciation is incorrect in allknown languages. I believe that this novel pronunciation was invented by my father.”)da http://en.wikipedia.org/wiki/Stephen_Cole_Kleene
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 47 / 69
http://en.wikipedia.org/wiki/Stephen_Cole_Kleenehttp://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene L3 ⊆ LdfTesi L3 ⊆ Ldf / I
Dim. Sia L ∈ L3 cioè ∃G = (Σ,V , S,P),G di tipo 3: L(G) = LSi deve costruire un DFAM = (Σ,Q, δ, q0, F) tale cheL(M) = L(G)
Algoritmo (dalle grammatiche agli automi)Input: G = (Σ,V , S,P),G di tipo 3Output: M = (Σ,Q, δ, q0, F) ∈ DFA1 Σ alfabeto di ingresso perM2 Q = V ∪ {q}, q 6∈ V3 q0 = S4 F = {q} ∪ {B | B −→ � ∈ P}5 δ : Q× Σ −→ ℘(Q)
1 ∀B −→ aC ∈ P : C ∈ δ(B, a)2 ∀B −→ a ∈ P : q ∈ δ(B, a)
B Ca
B qa
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 48 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene L3 ⊆ LdfTesi L3 ⊆ Ldf / II
Osservazione l’algoritmo può generare NFA (passi 5.1 e 5.2)Occorre dimostrare anche la correttezza dell’automa:L(G) = L(M)
L(G) ⊆ L(M): siaw = a1a2 · · · ak ∈ L(G)w può essere generata con una derivazione:S =⇒ a1X2 =⇒ a1a2X3 =⇒ · · · =⇒ a1a2 · · ·Xk =⇒a1a2 · · · akPer sua def.,M, prendendo in inputw, compie una serie ditransizioni che portano da S a X1,X2, . . . ,Xk fino a qL(M) ⊆ L(G): analogamente
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 49 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Ldf ⊆ L3Tesi (alt.) Ldf ⊆ L3
Dim. datoM si deve costruire G di tipo 3 tale che L(G) = L(M)Algoritmo (dagli automi alle grammatiche)Input: M = (Σ,Q, δ, q0, F) ∈ NFAOutput: G = (Σ,V , S,P) lineare1 Σ alfabeto di ingresso perM2 V = {A0, . . . ,A|Q|−1} |V | = |Q|3 S = A04 P = {Ai −→ aAj | qj ∈ δ(qi, a)} ∪
{Ai −→ a | δ(qi, a) ∈ F}
L(G) = L(M) per esercizio
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 50 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Ldf ⊆ LregTesi Ldf ⊆ Lreg / I
Dim. Sia L ∈ Ldf.Per def. ∃M = (Σ,Q, δ, q0, F) ∈ DFA tale che: L(M) = LSupponiamo Q = {q0, q1, . . . , qn}Si definiscono (∀i, j ∈ {0, . . . ,n}) i linguaggi:
Rij = {w ∈ Σ∗ | δ̂(qi,w) = qj}
contenenti le stringhe che fanno transitareM da qi a qjPer def. di linguaggio accettato da DFA, risulta:
L(M) =⋃qj∈F
R0j
quindi si deve dimostrare che ogni linguaggio Rij sia regolareN. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 51 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Ldf ⊆ LregTesi Ldf ⊆ Lreg / IISi definiscono:Rkij = {w ∈ Σ∗ | δ̂(qi,w) = qj senza transitare in qk, qk+1, . . . , qn}Osservato che: Rn+1ij = Rij, si dimostra per induzione su k che
Rkij ∈ Lreg ∀i, j ∈ {0, . . . ,n}
(k = 0) R0ij = {w ∈ Σ∗ | δ(qi,w) = qj} ∈ Lreg perché finito(k > 0) Per ipotesi induttiva: Rkij ∈ Lreg ∀i, j ∈ {0, . . . ,n}Dimostriamo che Rk+1ij ∈ LregSiaw ∈ Rk+1ij .Per definizione di Rk+1ij , la lettura diw non fa transitare
M in nessuno degli stati qk+1, qk+2, . . . , qnN. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 52 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Ldf ⊆ LregTesi Ldf ⊆ Lreg / III
qi qj
qk
transito per stati da q0 a qk−1
w1 wm
wk
I casi sono due:1 w non fa transitareM nemmeno attraverso qk,quindiw ∈ Rkij (e Rkij è regolare per ipotesi ind.)2 w fa transitareM in qk e risulta concatenazione dim > 1 sottostringhe:
w = w1w2 · · ·wm−1wm
con:w1 ∈ Rkik wt ∈ Rkkk 1 < t < m wm ∈ Rkkj
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 53 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Ldf ⊆ LregTesi Ldf ⊆ Lreg / IV
Si può scrivere: w ∈ Rkik · (Rkkk)m−2 · Rkkj (m > 1)per cui: w ∈ Rkik · (Rkkk)∗ · RkkjNe consegue allora che: Rk+1ij ⊆ Rkij ∪ Rkik · (Rkkk)∗ · Rkkjma ovviamente vale anche: Rkij ∪ Rkik · (Rkkk)∗ · Rkkj ⊆ Rk+1ijDa Rk+1ij = Rkij ∪ Rkik · (Rkkk)∗ · Rkkj segue Rk+1ij ∈ Lregin quanto espresso attraverso unione, prodotto e iterazione dilinguaggi che sono regolari (per ipotesi induttiva)Risulta dimostrato che ∀k ∈ {0, . . . ,n} : Rkij ∈ Lreg perciò
L(M) =⋃qj∈F
R0j =⋃qj∈F
Rn+10j
è regolare perché unione di linguaggi regolariN. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 54 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Ldf ⊆ Lreg
Algoritmo alternativo per Ldf ⊆ Lreg[Hopcroft et al.,(2009), Linz(2012)]eliminando uno stato alla volta, occorre preservare icammini che portano dallo stato iniziale a stati finalisi considerano gli (immediati) predecessori q1, . . . , qk esuccessori p1, . . . , pm dello stato s da eliminarearchi etichettati con espr. regolari anziché con simboli:infinite parole possono portare da uno stato ad un altro
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 55 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Ldf ⊆ Lreg
q1 p1
qk pm
sS
Q1
Qk
P1
Pm
R11
R1m
Rk1
Rkm
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 56 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Ldf ⊆ Lreg
eliminando s, per ogni (qi, pj), si etichetta l’arco con:Rij + QiS∗Pj
(un arco assente nel DFA originario sarebbe etichettato con ∅)q1 p1
qk pm
R11 + Q1S∗P1R1m + Q1S ∗Pm
Rk1+QkS∗P1
Rkm + QkS∗Pm
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 57 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Ldf ⊆ LregAlgoritmo (dagli automi alle espressioni regolari)
per ogni stato finale q ∈ Fsi eliminano tutti gli stati tranne q0 e q:applicando l’algoritmo si produce un automa con archietichettati da espr. regolariif q 6= q0 allora risulta un automa a due stati⇒ soluzione: (R∗ + SU∗T)∗SU∗else risulta un automa ad un stato⇒ soluzione: R∗
return somma di tutte le espr. regolari ottenute, al variare di q
q0 q
RS
U
Tq0
R
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 58 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Ldf ⊆ LregEsempio
A B C D
0,11 0,1 0,1
A B C D
0 + 11 0 + 1 0 + 1
A C D
0 + 11(0 + 1) 0 + 1
A D
0 + 11(0 + 1)(0 + 1)
RAD = (0 + 1)∗1(0 + 1)(0 + 1)
A C
0 + 11(0 + 1)
RAC = (0 + 1)∗1(0 + 1)R = RAC + RAD = (0 + 1)∗1(0 + 1)(0 + 1) + (0 + 1)∗1(0 + 1)
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 59 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Ldf ⊆ LregEsempio
q0 q1
q2 q3
a a
b
b
a b b//////
//////
q0
q2 q3
a a
b
ab b + bb
q0
q3
ab∗ab
ab + bb
(R∗ + SU∗T)∗SU∗
R = ab∗ab S = aT = b + bb U = ∅
R03 = ((ab∗ab)∗ + a(b + bb))∗aN. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 60 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Lreg ⊆ L3Tesi Lreg ⊆ L3 / I
Sia L ∈ Lreg quindi vale una delle seguenti condizioni:L è finitoL = L1 ∪ L2 con L1,L2 regolariL = L1 · L2 con L1,L2 regolariL = (L1)∗ con L1 regolare
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 61 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene Lreg ⊆ L3Tesi Lreg ⊆ L3 / II
Dim. per induzione sulla costruzione di Lbase L finito L = {w1,w2, . . . ,wn} allora si può scrivere comeunione di linguaggi lineari Li che generano ognuno unastringa diwi e la classe L3 è chiusa rispetto all’unione:
L =n⋃i=0Li
Si può facilmente dimostrare che ∀i ∈ {0, . . . ,n} : Li ∈ L3passo In tutti i tre casi i linguaggi L1 e L2 sono lineari per ipotesidi induzioneAnche la loro unione/concatenazione/iterazione è in L3 perla chiusura di L3 rispetto a queste operazioniQuindi L ∈ L3N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 62 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene L3 ⊆ LregTesi (alt.) L3 ⊆ Lreg / I
Sia L ∈ L3 e sia G tale che L(G) = L.Supponiamo4 per semplicità che � 6∈ Lsi trasforma ogni produzione in una equazione lineare destra:A −→ a1B1| · · · |anBn|b1| · · · |bmdiventaA = a1B1 + · · ·+ anBn + b1 + · · ·+ bmsi risolve il sistema usando le regole:
sostituzioneeliminazione della ricorsione:A = α1A+ · · ·+ αnA+ β1 + · · ·+ βmdiventaA = (α1 + · · ·+ αn)∗(β1 + · · ·+ βm)
l’espressione regolare sarà quella corrispondente ad S4Se � ∈ L allora calcolare R′ per L \ {�} e poi R = R′ + � per L.
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 63 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene L3 ⊆ LregEsempioS −→ aS|bA|�A −→ aA|bS|�eliminando subito la produzione A −→ �:S −→ aS|bA|b|�A −→ aA|bS|aSi costruisce il sistema:{S = aS+ bA+ b + �A = aA+ bS+ aeliminando la ricorsione su A:{S = aS+ bA+ b + �A = a∗(bS+ a)sostituendo A nella def. di S, si ha:S = aS+ b(a∗(bS+ a)) + b + �
= aS+ ba∗bS+ ba∗a + b + �= (a + ba∗b)S+ ba∗a + b + �
A = a∗(bS+ a)eliminando la ricorsione su S:{S = (a + ba∗b)∗(ba∗a + b + �)A = · · ·Quindi la soluzione è RS = (a + ba∗b)∗(ba∗a + b + �)
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 64 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene EserciziEsercizi I
1 Data la grammatica lineare G = (Σ,V , S,P) conΣ = {a,b,c}, V = {S,A,B} eP = {S −→ bA|aS|b,
A −→ aB|cS|a,B −→ bA|cB|c}determinare una espressione regolare per L(G)
2 Sia L = L(R) ove R = (aa + aaa)∗costruire un automa che riconosce Ltrasformare l’NFA del punto 1. in DFA
3 Sia L = L(R) ove R = ab(bb)∗ctrovare un automa (NFA) per riconoscere Ltrasformare l’automa NFA nell’DFA equivalente
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 65 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene EserciziEsercizi II
4 Data la grammatica lineare G = (Σ,V , S,P) conΣ = {a,b}, V = {S,B} eP = {S −→ aB, B −→ aB|bS|a}determinare un automa DFAM tale che: L(M) = L(G)
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 66 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene EserciziEsercizi III
Esercizio 2. Sia L = L(R) ove R = (aa + aaa)∗1. costruire un automa che riconosce L2. trasformare l’NFA del punto 1. in DFA1. Dato Σ = {a}, determiniamo le grammatiche G1 perL1 = {aa} e G2 per L2 = {aaa}:G1 = (Σ,V1, S1,P1) con V1 = {S1,A} eP1 = {S1 −→ aA, A −→ a}G2 = (Σ,V2, S2,P2) con V2 = {S2,B,C} eP2 = {S2 −→ aB, B −→ aC, C −→ a}Sia G3 = (Σ,V3, S3,P3) la grammatica per L3 = L1 ∪ L2:con V3 = V1 ∪ V2 ∪ {S3} = {S3, S1, S2,A,B,C} eP3 ={S3 −→ w | S1 −→ w ∈ P1}∪
{S3 −→ w | S2 −→ w ∈ P2} ∪ P1 ∪ P2={S3 −→ aA | aB} ∪ P1 ∪ P2(contiene produzioni inutili e quindi NT superflui: S1,S2)
N. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 67 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
Teorema di Kleene EserciziEsercizi IV2. L’automa a stati finiti si ottiene mediante l’algoritmo dato nelladimostrazione del teorema di Kleene:
Q = V ∪ {q} = {S,A,B,C, q}q0 = SF = {q, S}δ definita da:
S
A q
B C
a
a
aa
a
a aδ a
→ ∗S {A,B}A {S, q}B {C}C {S, q}∗q ∅
Per esercizio: trasformare l’NFA in un DFAN. Fanizzi Linguaggi di prog.+Lab Linguaggi Regolari 17 marzo 2014 68 / 69
http://www.di.uniba.it/~fanizzihttp://www.di.uniba.it/~fanizzi/corsi/lp
-
RiferimentiAusiello G.; D’Amore F.; Gambosi G. 2003.Linguaggi, Modelli, Complessità.FrancoAngeli.Cohen D. I. 1996.Introduction to Computer Theory.Wiley.Hopcroft J. E.; Motwani R.; Ullman J. D. 2009.Automi, Linguaggi e Calcolabilità.Pearson Italia, 3a edizione.Linz P. 2012.An Introduction to Formal Languages and Automata.Jones & Bartlett, 5a edizione.Moll R. N.; Arbib M. A.; Kfoury A. J. 1988.An introduction to formal language theory.Springer.Sipser 2005.Introduction to the theory of computation.Thomson, 2a edizione.Sudkamp 2006.Languages and Machines.Addison-Wesley, 3a edizione.
Automi a Stati FinitiAutomi DeterministiciAutomi Non-deterministiciEquivalenza tra DFA e NFAEsercizi
Espressioni RegolariDefinizioniCorrispondenza Linguaggi/Espressioni RegolariProprietà delle Espressioni RegolariEsercizi
Teorema di KleeneL3LdfLdfL3LdfLregLregL3L3LregEsercizi