Introduzione: Linguaggi Formali -...

Introduzione:

Linguaggi Formali

Nicola FanizziCorso di Linguaggi di ProgrammazioneDipartimento di InformaticaUniversità degli Studi di Bari10 marzo 2014

Sommario

1 Nozioni PreliminariAlfabeti e StringheParti di una stringaProdottoProdotto e Struttura diMonoidePotenze e Chiusure diAlfabeti2 Linguaggi FormaliDefinizioneOperazioni sui LinguaggiProprietà delleOperazioni

3 Rappresentazioni Finite peri LinguaggiGrammatiche GenerativeDerivazioniLinguaggio Generato da unaGrammaticaEsercizi sulle GrammaticheLa Gerarchia di ChomskyTipi di Grammatiche e Classidi LinguaggiTeorema della GerarchiaAutomiSchema di una MacchinaTransizioniComputazioniDeterminismoTipologieN. Fanizzi Linguaggi di prog.+Lab Introduzione: Linguaggi Formali 10 marzo 2014 2 / 52

http://www.di.uniba.it/~fanizzi

http://www.di.uniba.it/~fanizzi/corsi/lp

Nozioni Preliminari Alfabeti e StringheAlfabeti e Stringhe I

Un alfabeto è un insieme di simboli finito e non vuoto disimboliEsempi

Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} alfabeto delle cifre decimaliΣ′ = {a, b, c, . . . , z} alfabeto delle lettere (minuscole)Una stringa (o parola, word)w su un alfabeto Σè una sequenza finita di simboli s1s2 · · · sn tale che∀i ∈ {1, . . . ,n} : si ∈ Σ.La lunghezza diw è pari ad n e si denota con |w|.La stringa vuota, denotata1 con ε, è la parola priva di simboli(|ε| = 0)Esempio Alcune stringhe su Σ′ sono aaba, aca, cbaa, b, . . .Dato Σ = {0, 1} siaw = 0010110 con |w| = 7

N. Fanizzi Linguaggi di prog.+Lab Introduzione: Linguaggi Formali 10 marzo 2014 3 / 52



Nozioni Preliminari Alfabeti e StringheAlfabeti e Stringhe II

Si denota con Σ∗ l’insieme di tutte le stringhe su Σ.Osservazione ∀Σ: ε ∈ Σ∗

Esempio Dato Σ = {0, 1} risultaΣ∗ = {ε, 0, 1, 00, 01, 10, 11, 000, 001, . . .}Dataw = s1s2 · · · sn su Σ, la sua stringa riflessa2 (oinversione) saràwR = snsn−1 · · · s1, definita anche con:wR =

{w |w| < 2

svR w = vs, s ∈ Σ

Esempio Dataw = abbaa : wR = aabba

1Su alcuni testi denotata con ε.2Sew = wR, la stringaw si dice palindromaN. Fanizzi Linguaggi di prog.+Lab Introduzione: Linguaggi Formali 10 marzo 2014 4 / 52



Nozioni Preliminari Alfabeti e StringheNomenclatura: parti di una stringa

Data la stringaw = uvy

tale che u, v, y ∈ Σ∗,u è un prefisso diw,y è un suffisso diw ev è una sottostringa diwEsempio w = 00110

prefissi diw: ε, 0, 00, 001, 0011 ewsuffissi diw: ε, 0, 10, 110, 0110 ewsottostringhe diw:ε, 0, 1, 00, 01, 10, 11, 001, 011, 110, 0011, 0110 ew




Nozioni Preliminari ProdottoProdotto e Struttura di Monoide I

Date u, v ∈ Σ∗ tali che u = s1 · · · sm e v = s′1· · · s′n la

concatenazione (o prodotto) di u e v è data dalla stringa uv(denotata anche u · v) di lunghezzam + n con i primimsimboli uguali a quelli di u e gli ultimi n uguali a quelli di v:w = uv = s1 · · · sms′

1· · · s′n

Il prodotto · : Σ∗ × Σ∗ → Σ∗

ha per elemento neutro εgode della proprietà associativa: u · (v ·w) = (u · v) ·wnon è commutativopertanto (Σ∗, ·) è un monoide (non commutativo)




Nozioni Preliminari ProdottoProdotto e Struttura di Monoide II

Proposizione∀u, v ∈ Σ∗ : |uv| = |u|+ |v|

Dim.(per esercizio.)




Nozioni Preliminari ProdottoPotenze e Chiusure di Alfabeti

Dataw ∈ Σ∗, potenza k-esima diw:wk =

{ε k = 0

wwk−1 k > 0Potenza di un alfabeto:Σk =

{{ε} k = 0

Σ · Σk−1 k > 0Σ1 = ΣΣ2 = Σ · Σ = {s1s2 | s1, s2 ∈ Σ}. . .

chiusura transitiva (o anche chiusura positiva) di ΣΣ+ =

⋃k>0Σk

chiusura riflessiva e transitiva (o anche chiusura star) di ΣΣ∗ = Σ+ ∪ {ε}




Linguaggi Formali DefinizioneLinguaggi Formali – Definizione I

DefinizioneUn linguaggio L su un alfabeto Σ è un sottoinsieme di Σ∗:

L ⊆ Σ∗

Osservazioni

∅, {ε} e Σ sono linguaggi su Σ (|∅| = 0 6= 1 = |{ε}|)Su alcuni testi: Λ ≡ ∅




Linguaggi Formali DefinizioneLinguaggi Formali – Definizione II

EsempiLinguaggio finito L = {ε, aab, aaaabb}.Linguaggio infinito L = {aib2i | i ≥ 0}.Linguaggio delle parentesi ben formate L ⊆ {(, )}∗:(())() ∈ L e()(()()) ∈ Lmentre(()() 6∈ L




Linguaggi Formali Operazioni sui LinguaggiOperazioni sui Linguaggi

Dati due linguaggi L e L′ definiti sullo stesso alfabeto Σ:prodotto L · L′ = {w = w1 ·w2 ∈ Σ∗ | w1 ∈ L ∧w2 ∈ L′}iterazione L∗ = {w1 . . .wn ∈ Σ∗ | ∀n∀i : wi ∈ L, 0 ≤ i ≤ n}unione L ∪ L′ = {w ∈ Σ∗ | w ∈ L ∨w ∈ L′}

complemento L = {w ∈ Σ∗ | w 6∈ L}intersezione L ∩ L′ = {w ∈ Σ∗ | w ∈ L ∧w ∈ L′}

potenza Lk =

{{ε} se k = 0

Lk−1 · L se k > 0chiusura L+ =

⋃k>0 Lk chiusura positiva(transitiva, non riflessiva)NB: L∗ = L0 ∪ L+ = {ε} ∪ L+

(transitiva e riflessiva)riflessione LR = {wR | w ∈ L}




Linguaggi Formali Proprietà delle OperazioniProprietà delle Operazioni sui Linguaggi

Dati i linguaggi L,L′,L′′ definiti sullo stesso alfabeto Σ:1. (L · L′) · L′′ = L · (L′ · L′′) proprietà associativa2. L · L′ 6= L′ · L non commutatività3. L · {ε} = {ε} · L = L elemento neutroQuindi 〈℘(Σ∗), ·〉 è un monoide.

Si noti che Σ∗ può essere ottenuto come chiusura riflessiva dellinguaggio Σ (delle stringhe di lunghezza unitaria)4. L · ∅ = ∅ · L = ∅ elemento assorbente35. Se ε ∈ L: L′ ⊆ L · L′ e L′ ⊆ L′ · L6. ε ∈ L∗7. ∅∗ = {ε}3Su alcuni testi Λ = ∅




Linguaggi Formali Proprietà delle OperazioniEsempi

EsempioDati i linguaggi L1 = {a2n | n ≥ 0} e L2 = {b, cc}L1 · L2 = {b, cc, aab, aacc, aaaab, aaaacc, . . .}L2 · L1 = {b, cc, baa, ccaa, baaaa, ccaaaa, . . .}

verificata quindi la proprietà 5)Inoltre:L1 ∪ L2 = L2 ∪ L1 = {ε, b, cc, aa, aaaa, aaaaaa, . . .}(L1)∗ = {ε, aa, aaaa, aaaaaa, aaaaaaaa, . . .}(L2)∗ = {ε, b, cc, bb, bcc, ccb, bbb, cccc, . . .}(L2)0 = {ε}(L2)1 = {b, cc}(L2)2 = {bb, bcc, ccb, cccc} . . .(L2)+ = {b, cc, bb, bcc, ccb, bbb, cccc, . . .}




Rappresentazioni Finite per i LinguaggiRappresentazioni Finite per i Linguaggi

I linguaggi possono essere riguardati sotto due punti di vista:Generativo: come generare le parolew di L ?

L potrebbe essere infinito (estensione) maenumerabile mediante un numero finito di regole(intensione)strumento formale: grammatiche generativeRiconoscitivo: come decidere sew ∈ L ?È il punto di vista dei compilatori in fase d’analisisintattica (o lessicale)strumento formale: automi




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeGrammatica Generativa I

Definizione (Grammatica)Una grammatica generativa è una quadrupla G = (Σ,V , S,P)con

Σ alfabeto terminale, ins. finito, non vuotoV alfabeto non terminale (NT), ins. finito con Σ ∩ V = ∅S ∈ V simbolo di partenza (start) o distintivo (assioma)P insieme delle regole di produzione (α, β), denotate anchecon

α −→ βdoveα ∈ (Σ ∪ V)+ e contiene almeno un non-terminaleβ ∈ (Σ ∪ V)∗ può essere anche εUna regola α −→ ε si dice ε-produzione




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeGrammatica Generativa II

Osservazioni

(α, β) ∈ [(Σ ∪ V)∗ · V · (Σ ∪ V)∗]× (Σ ∪ V)∗

Si usa la notazione abbreviataα −→ β1 | β2 | . . . | βn

per riassumere le produzioni:α −→ β1α −→ β2...α −→ βn




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeDerivazioni I

Data G = (Σ,V , S,P) e due stringhe φ = γαδ ∈ (Σ ∪ V)+ eψ = γβδ ∈ (Σ ∪ V)∗ con α, β, γ, δ ∈ (Σ ∪ V)∗,φ deriva direttamente ψ, denotato con φ =⇒ ψ, sse∃α −→ β ∈ PDato un ordinamento su P,=⇒

idenota una derivazione

diretta nella quale si applica la produzione i-esima α i−→ β∗

=⇒ chiusura transitiva e riflessiva di=⇒+

=⇒ chiusura transitiva di=⇒:φ deriva ψ, denotato con φ ∗

=⇒ ψ, sseφ = ψ oppure∃φ0, φ1, . . . , φn ∈ (Σ ∪ V)+, con φ0 = φ, e φn = ψ, tali che:φi−1 =⇒ φi ∀i ∈ {1, . . . ,n}




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeDerivazioni II

n=⇒ denota una derivazione in n passi(n lunghezza della derivazione)φ ∈ (Σ ∪ V)∗ è una forma di frase di G sse: S ∗

=⇒ φ

Esempio Data G = ({a, b}, {S}, S,P) conP = {S 1−→ ε, S 2−→ aSbb}

S=⇒2

aSbb=⇒2

aaSbbbb=⇒1

aabbbb = a2b4




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeDerivazioni III

Esempio Data G = ({a, b}, {A,B,C, S}, S,P) conP = {S −→ aAS | bBS | C,

Aa −→ aA,Ba −→ aB,Ab −→ bA,Bb −→ bB,BC −→ Cb,AC −→ Ca,C −→ ε}

Si genera L(G) = {ww | w ∈ {a, b}∗}

S=⇒1

aAS=⇒2

aAbBS=⇒3

aAbBC=⇒6

abABC =⇒8

abACb=⇒9

abCab=⇒10

abab




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeLinguaggio Generato da una Grammatica

Definizione (Linguaggio Generato da una Grammatica)Data la grammatica G = (Σ,V , S,P),dicesi linguaggio generato dalla grammatica Gl’insieme delle stringhe di simboli terminali derivabili da S:

L(G) = {w ∈ Σ∗ | S ∗=⇒ w}




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeEsempi I

Grammatica per generare L = {anbn+1 | n > 0}:G = ({a, b}, {S,A}, S,P) con

P = {S −→ Ab,A −→ aAb | ab}

Grammatica per generare il linguaggio dei numeri binaripari:G1 = ({0, 1}, {S1,U}, S1,P1) con

P1 = {S1 −→ 0 | 0S1 | US1, U −→ 1}




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeEsempi II

Grammatica per generare L = {1n0 | n ≥ 0}:G2 = ({0, 1}, {S2,A}, S2,P2) con

P2 = {S2 −→ A0 | 0, A −→ A1 | 1}

Osservazione L(G2) ( L(G1)




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeEsempi III

Lquad = {an2 | n > 0} [Ausiello et al.,(2003)]Gquad = ({a}, {S,A,B, E,R,X}, S,P)

P =

S −→ BRAEB −→ BRAA

RA −→ aARRa −→ aRRE −→ EB −→ X

XA −→ XXa −→ aXXE −→ ε




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeEsempi IV

idea: 1+ 3+ 5+ · · ·+ (2n− 1) = n2

B = BEGIN E = END: segnapostole prod. 1 e 2 (S −→ BRAE, B −→ BRAA)creano forme di frase B(RAA)kRAE per qualche k ≥ 0ogni R ha un numero dispari di A alla sua destraogni R si sposta verso destra (RA −→ aAR Ra −→ aR)creando una nuova a per ogni A che si incontrala R cade quando incontra la E (RE −→ E)infine B si trasforma in X facendo cancellare le A, la X e la E(prod. 6− 9)




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeEsempi V

S =⇒ BRAE =⇒ BaARE =⇒ BaAE =⇒ XaAE =⇒ aXAE =⇒aXE =⇒ a

S ∗=⇒ BRAARAE =⇒ BRAARAARAE =⇒ BaARARAARAE =⇒

BaARARAAaARE =⇒ BaAaARRAAaARE =⇒BaAaARaARAaARE =⇒ BaAaARaARAaAE =⇒BaAaARaAaARaAE =⇒ BaAaAaRAaARaAE =⇒BaAaAaaARaARaAE =⇒ BaAaAaaAaRARaAE =⇒BaAaAaaAaaARRaAE =⇒ BaAaAaaAaaARaRAE =⇒BaAaAaaAaaAaRRAE =⇒ BaAaAaaAaaAaRaARE =⇒BaAaAaaAaaAaRaAE =⇒ BaAaAaaAaaAaaRAE =⇒BaAaAaaAaaAaaaARE =⇒ BaAaAaaAaaAaaaAE =⇒XaAaAaaAaaAaaaAE =⇒ aXAaAaaAaaAaaaAE =⇒aXaAaaAaaAaaaAE =⇒ aaXAaaAaaAaaaAE =⇒aaXaaAaaAaaaAE ∗

=⇒ aaaaaaaaaXAE =⇒ aaaaaaaaaXE =⇒aaaaaaaaa = a9




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeEquivalenza e Correttezza

Osservazione Dato un linguaggio L, possono esistere diversegrammatiche che lo generanoDue grammatiche G e G′ sono equivalenti sse L(G) = L(G′)In generale, dati un linguaggio L ed una grammatica G, nonesiste un algoritmo in grado di dimostrare che L = L(G):

TeoremaIl problema generale di dimostrare la correttezza di unagrammatica non è risolvibile per via algoritmica

L’equivalenza si può dimostrare per induzioneL ⊆ L(G), i.e. G genera solo stringhe di LL(G) ⊆ L, i.e. L contiene solo stringhe generabili da G




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeEsercizi

1 Determinare una grammatica che generi {anbn | n > 0}.2 Data G = (Σ,V , S,P) con Σ = {0, 1}, V = {S,A,B} e

P = {S −→ 0B|1A, A −→ 0|0S|1AA, B −→ 1|1S|0BB}determinare L(G).3 Determinare una grammatica che generi {anb2n | n > 0}.4 Determinare una grammatica che generi{akbnc2k | n, k > 0}

5 Data G = ({a, b}, {S}, S,P) conP = {S −→ ε | SS | aSb | bSa}, dimostrare cheL(G) = {w | na(w) = nb(w)}

6 Data G = ({a, b, c}, {S,A}, S,P) conP = {S −→ aSc | A, A −→ bAc | ε} dimostrare cheL(G) = {anbmcn+m | n + m > 0}.

7 Data G = ({a, b, c}, {S,A}, S,P) conP = {S −→ Ab, A −→ Sa}, dimostrare che L(G) = ∅.

8 Definire una grammatica che generi{0n1m2k | n = m ∨m = k} e dimostrarne la correttezza.




Rappresentazioni Finite per i Linguaggi Grammatiche Generative

Esempio (6.)Data G = ({a, b, c}, {S,A}, S,P) conP = {S −→ aSc | A, A −→ bAc | ε} dimostrare cheL(G) = {anbmcn+m | n + m > 0}.

Dim.Occorre dimostrare (per induzione):L ⊆ L(G): sulla lunghezza delle derivazioni da S di GL(G) ⊆ L: sulla lunghezza delle stringhe di L




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeL(G) ⊆ LSi osservi che, essendo P = {S −→ aSc | A, A −→ bAc | ε},ogni forma di frase di G è del tipo:

akSck , con k ≥ 0 oppureakbjAck+j, con k, j ≥ 0

Ogni z ∈ L(G) è generata da derivazioni del tipo:S k

=⇒ akSck 1=⇒ akAck j

=⇒ akbjAcjck 1=⇒ akbjck+j

Quindi z ∈ L.L ⊆ L(G)Sia z = anbmcn+m ∈ L.Può essere generata con una derivazione del tipo:

S n=⇒ anScn 1

=⇒ anAcn m=⇒ anbmAcmcn 1

=⇒ anbmcn+m

Quindi, esistendo una derivazione, z ∈ L(G).N. Fanizzi Linguaggi di prog.+Lab Introduzione: Linguaggi Formali 10 marzo 2014 29 / 52



Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeGerarchia delle Grammatiche

In base alla forma delle produzioni,si distinguono i tipi seguenti:0 grammatiche generative (a forma di frase), senzalimitazioni:

αAβ −→ ω A ∈ V , α, β, ω ∈ (Σ ∪ V)∗

1 grammatiche dipendenti da contesto (o context-sensitive,CS):αAβ −→ αωβ A ∈ V , α, β ∈ (Σ ∪ V)∗, ω ∈ (Σ ∪ V)+

S −→ ε se S non compare in alcuna parte destra2 grammatiche libere da contesto (o context-free, CF):

A −→ ω A ∈ V , ω ∈ (Σ ∪ V)∗

3 grammatiche lineari destre (o regolari):A −→ sB A,B ∈ V , s ∈ ΣA −→ σ A ∈ V , σ ∈ Σ ∪ {ε}

Un linguaggio è di tipo i se viene generato da una grammatica di tipo iN. Fanizzi Linguaggi di prog.+Lab Introduzione: Linguaggi Formali 10 marzo 2014 30 / 52



Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeTipi di Grammatiche e Classi di Linguaggi I

Esistono linguaggi per cui non esiste una grammaticacorrispondente0 La classe più ampia nell’ambito dei linguaggi descrivibili congrammatiche.

L = {anbf (n) | n > 0}dove f è una qualunque funzione RE [Ausiello et al.,(2003)]Le grammatiche ammettono prod. che accorciano le forme difrase.Quelle che non accorciano si dicono grammatichemonotòne,ossia con produzioni: α −→ β con |α| ≤ |β|Esempi grammatiche G = (Σ,V , S,P)

GquadP = {S −→ aSa|aAb|aAa|ε, aAa −→ a|ε, aaAb −→ b|ε}P = {S −→ aAb, aA −→ aaAb, A −→ ε}(ma il ling. generato è più semplice, quale?)




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeTipi di Grammatiche e Classi di Linguaggi II

1 Su alcuni testi prod. CS definite come prod. monotone:Per un teorema: i ling. monotoni sono tutti di tipo 1 (anziché0).Trasformando la gramm. monotonaP = {S −→ E | ε,C −→ a, D −→ b,

E −→ aAE | bBE | Ca | Db,Aa −→ aA, Ab −→ bA,Ba −→ aB, Bb −→ bB,AC −→ Ca, BC −→ Cb,AD −→ Da, BD −→ Db}

Esempi G = (Σ,V , S,P)

P = {S −→ aSa|aAb|aAa, aA −→ aa, Ab −→ aab}P = {S −→ aBSc|abc, Ba −→ aB, Bb −→ bb}quale ling. genera ?




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeTipi di Grammatiche e Classi di Linguaggi III

2 La classe usata per definire i ling. di programmazioneEsempi

G = ({(, )}, {S}, S, {S −→ () | SS | (S)}G = ({+, *, i, (, )}, {E,T, F}, E,P)con P = {E −→ E+T|T, T −→ T*F|F, F −→ i|(E)}

3 Lineari destre: a destra di ogni produzione,e quindi nelle f.d.f. di ogni derivazione, al più unnon-terminale (come simbolo più a destra).Si dicono anche regolari perché i ling. generati sonorappresentabili tramite espressioni regolarilinguaggi finitilinguaggio delle stringhe binarie {0, 1}∗linguaggio delle stringhe su {0, 1} con un numero pari di 1

Esempi

G = ({a, b}, {S}, S, {S −→ aS|b}) genera L = {anb|n ≥ 0}




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeTipi di Grammatiche e Classi di Linguaggi IV

I linguaggi regolari si possono generare anche tramitegrammatiche lineari sinistre, ossia con produzioni del tipo:A −→ β A ∈ V , β ∈ (V · Σ) ∪ Σ ∪ {ε}

G′ = ({a, b}, {S,A}, S, {S −→ Ab|b, A −→ Aa|a}): L(G′) = L




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeTeorema della Gerarchia I

Teorema (gerarchia)Dato un alfabeto Σdenotate le classi di linguaggi nel seguente modo

Li = {L ⊆ Σ∗ | ∃G grammatica di tipo i : L = L(G)}

risulta: L3 ( L2 ( L1 ( L0L3 REG

L2 CFL1 CS

L0 RE

L3 REGL2 CF

L1 CSL0 RE

Dim. Si dimostra provando la catena di inclusioni:N. Fanizzi Linguaggi di prog.+Lab Introduzione: Linguaggi Formali 10 marzo 2014 35 / 52



Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeTeorema della Gerarchia II

(L3 ( L2) Si osservi che L3 ⊆ L2 per definizione, occorre soloprovare l’inclusione stretta usando unlinguaggio separatore, per es. {akbk | k > 0}(L2 ( L1) Per la forma delle produzioni vale L2 ⊆ L1,tranne nel caso di ε-produzioni: A −→ ε con A 6= S

Per il lemma della stringa vuota,∀L ∈ L2 ∃G CF senza ε-regole,tranne S −→ ε se ε ∈ L,tale che L(G) = L

Linguaggio separatore: {akbkck | k > 0}(L1 ( L0) Per definizione L1 ( L0.Linguaggio separatore: L tale che le stringhe di L sianoenumerabili ma non quelle di L̄

∃ML mdT che ∀z ∈ L,ML termina accettando z,mentre ∃z̄ ∈ L̄ per la qualeML divergeN. Fanizzi Linguaggi di prog.+Lab Introduzione: Linguaggi Formali 10 marzo 2014 36 / 52



Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeGenerazione della Stringa Vuota I

Per i tipi 1, 2, 3, ε-produzioni sono ridondanti;[Ausiello et al.,(2003)]la generazione della stringa vuota può essere limitata all’assiomaS −→ ε

Se G = (Σ,V , S,P) di tipo 1, 2 o 3 (senza ε-produzioni) generaL, per generare L ∪ {ε} è sufficiente utilizzareG′ = (Σ,V ∪ {S′}, S′,P′) dove

P′ = P ∪ {S′ −→ ε} ∪ {S′ −→ β | S −→ β ∈ P}

Se S non appare nella parte destra di alcuna produzione,si può anche aggiungere S −→ ε senza conseguenzeN. Fanizzi Linguaggi di prog.+Lab Introduzione: Linguaggi Formali 10 marzo 2014 37 / 52



Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeGenerazione della Stringa Vuota II

Esempio

Data G = (Σ,V , S,P), conP = {S −→ aBSc|abc, Ba −→ aB, Bb −→ bb} tale cheL(G) = {anbncn|n > 0}.Per generare anche ε = a0b0c0, si definisceG′ = (Σ,V ∪ {S′}, S′,P′) con P′ = {S′ −→ ε|aBSc|abc} ∪ P

Data G = (Σ,V , S,P), conP = {S −→ Ub, U −→ ab|S}si genera L(G) = {abhbb | h ≥ 0}.Aggiungendo S −→ ε a P′, G′ genererebbe, oltre ε, anche lestringhe di {bbk | k ≥ 0}




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeGenerazione della Stringa Vuota III

TeoremaData G di tipo 0, esiste G′, ottenuta estendendo con opportuneε-produzioni una grammatica monotona (di tipo 1) equivalente a GDim. (cenni) Si aggiunge X −→ ε con X nuovo NT e sostituiscead ogni φ −→ ψ tale che |φ| > |ψ| > 0 con φ −→ ψ X · · ·X︸︷︷︸

|φ|−|ψ| volte

EsempioSia G = (Σ,V , S,P) con produzioni monotone tranne AB −→ C.Si può costruire G = (Σ,V ∪ {H}, S,P′), conP′ = P \ {AB −→ C} ∪ {AB −→ CH, H −→ ε}




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeGenerazione della Stringa Vuota IV

Nel caso di grammatiche di tipo 2 o 3 l’aggiunta di ε-produzioninon altera il potere generativo delle grammatiche:TeoremaData una grammatica G con produzioni libere (regolari) anchevuote, esiste una grammatica libera (regolare) G′ priva diε-produzioni, tale che:

L(G′) = L(G) \ {ε}

Dim. (cenni)tipo 2: algoritmo basato sull’individuazione dei NT annullabilitipo 3: più sempliceOsservazione Se ε ∈ L basta aggiungere S −→ ε




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeGenerazione della Stringa Vuota V

Esempi

La grammatica libera con produzioni{S −→ AB|aB|B, A −→ ab|aB, B −→ cX|X, X −→ ε}si modifica in{S −→ AB|aB|B, A −→ ab|aB, B −→ c|ε}e quindi in{S −→ AB|aB|B|A|a|ε, A −→ ab|aB|a, B −→ c}Nella grammatica regolare con produzioni{S −→ bX|aB, B −→ cX, X −→ ε}si elimina la produzione vuota riscrivendo nella forma:{S −→ b|aB, B −→ c}




Rappresentazioni Finite per i Linguaggi Grammatiche GenerativeLinguaggi, Grammatiche, Macchine

Riconoscitrici

Tipo Grammatiche Linguaggi Macchine

0 senza ricorsivamente macchinarestrizioni enumerabili (RE) di Turing— ricorsivi decider MdT(si fermano sempre)1 dipendenti da dipendenti da automi LBAcontesto (CSG) contesto (CSL) limitati lineramenteindicizzate indicizzati PDA a stack incorporatistack annidati + lettura pilaa riscrittura di alberi leggermente contestuali PDA a stack incorporatiTAG (mildly CS) EPDA2 libere liberi PDA(CFG) (CFL) non deterministicilibere liberi PDAdeterministiche (LL/LR) deterministici deterministici— a parole annidate FSA per NWLvisibly pushdown (NWL) FNWA3 lineari lineari automa a stati finiti(regolari) (regolari) FSA (NDA)— senza aciclicicicli finito




Rappresentazioni Finite per i Linguaggi AutomiAutomi

Modelli astratti di macchinein input su un nastro T , fatto da celle contenenti un simbolociascuna, stringhe su un dato alfabeto d’ingresso Σ

RO o RWlettura L-to-R (con/senza EOF)un simbolo alla voltapossono prevedere anche la produzione di output(analogamente)possono averememoria temporanea S: nastro illimitato,contenente simboli su un (diverso) alfabeto Γ

una unità di controllo a stati finiti determina ilfunzionamento della macchina




Rappresentazioni Finite per i Linguaggi AutomiSchema di una Macchina

· · · b b a a a aT

· · ·

q0q1

q2

q3 . . .qnδ

CU

γ1

γ2

γ2

γ3

γ1

S

H




Rappresentazioni Finite per i Linguaggi AutomiTransizioni

Ad ogni passo (tempo discreto):l’unità di controllo determina transizioni di stato in base a:

stato corrente qsimbolo in input dal nastro T(contenuto della memoria temp. S)secondo una funzione di transizione δ (programma)può anche (automi più complessi)

cambiare la memoria temp. Sprodurre un output su Tsi muove sul prossimo simbolo su T




Rappresentazioni Finite per i Linguaggi AutomiConfigurazioni della Macchina

Configurazione c diM determinata da:1 stato interno corrente dell’automa;2 contenuto di tutti i nastri di memoria;3 posizione di tutte le testine sui nastri.L’applicazione della funzione di transizione ad unaconfigurazione si dice transizione omossa o passocomputazionale dell’automa.δ induce una relazione di transizione tra configurazioni, cheassocia ad una configurazione una (o più di una) configurazionesuccessiva:date due configurazioni ci, cj

ci ` cj

indica che cj deriva da ci (per effetto dell’applicazione4 di δ)4A volte si trova `δ o `M , per maggiore precisione.N. Fanizzi Linguaggi di prog.+Lab Introduzione: Linguaggi Formali 10 marzo 2014 46 / 52



Rappresentazioni Finite per i Linguaggi AutomiComputazioni

Alcune configurazioni sono definite di accettazione.Tutte le altre sono considerate di non accettazione (o dirifiuto)Una computazione eseguita daM a partire da una config.iniziale c0 è una sequenza c0, c1, c2, . . . tale che ∀i : ci ` ci+1.∗` indica la chiusura transitiva e riflessiva della relazione `Se c0 ∗` cn con una seq. finita (massimale5)allora la computazione termina:computazione di accettazione se cn è una config. diaccettazione,altrimenti è una computazione di rifiuto

5ossia tale che 6 ∃c : cn∗` c.




Rappresentazioni Finite per i Linguaggi AutomiAutomi – Determinismo

deterministico ogni passo è determinato univocamente dallaconfigurazione correntec0 c1 c2 c3 c4 c5 · · ·

non-deterministico la configurazione corrente può determinaretransizioni alternative

c0 c1 c2

c3

c4

c5 · · ·

c6

c7

c8 · · ·

c9 · · ·




Rappresentazioni Finite per i Linguaggi AutomiTipologie di Automi

accettori6 output determinato dallo stato raggiunto (stati finali)decidono se la stringa sul nastro appartiene adun linguaggiorisposta sì/no

trasduttori in base alla stringa in input, producono una stringain output

6detti anche riconoscitori.N. Fanizzi Linguaggi di prog.+Lab Introduzione: Linguaggi Formali 10 marzo 2014 49 / 52



Rappresentazioni Finite per i Linguaggi AutomiRiconoscitore

q0 q1

q2

l,u

n

l,n,u

l,n,u




Rappresentazioni Finite per i Linguaggi AutomiTrasduttore

q0 q1(0,0)/0

(0,1)/1

(1,0)/1

(1,1)/0 (0,1)/0

(1,0)/0

(1,1)/1

(0,0)/1




Riferimenti

Ausiello 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.

Introduzione: Linguaggi Formali -...

Documents

Transcript of Introduzione: Linguaggi Formali -...