PumpLemma he e Derivazioni

37
Linguaggi Contestuali e Liberi da Contesto Nicola Fanizzi Corso di Linguaggi di Programmazione Dipartimento di Informatica Università degli Studi di Bari 18 marzo 2010 N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 1 / 37

Transcript of PumpLemma he e Derivazioni

Page 1: PumpLemma he e Derivazioni

Linguaggi Contestuali e Liberi da Contesto

Nicola FanizziCorso di Linguaggi di Programmazione

Dipartimento di InformaticaUniversità degli Studi di Bari

18 marzo 2010

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 1 / 37

Page 2: PumpLemma he e Derivazioni

1 Linguaggi ContestualiDefinizioniLinguaggi MonotoniTeoremi di Equivalenza sui Linguaggi Monotoni

2 Linguaggi Liberi da ContestoAlberi di Derivazione e Derivazioni CanonichePrincipio di sostituzionePumping Lemma per Linguaggi LiberiAmbiguità

3 EserciziEsercizio 2Esercizio 3Esercizio 1

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 2 / 37

Page 3: PumpLemma he e Derivazioni

Linguaggi Contestuali Definizioni

Grammatiche e Linguaggi Contestuali

Le grammatiche dipendenti da contesto sono caratterizzate peravere produzioni dei tipi seguenti:

1 yAz → ywzcon A ∈ V , y , z ∈ (X ∪ V )∗ e w ∈ (X ∪ V )+;

2 S→ λpurché S non compaia a destra di alcuna produzione;

I linguaggi generati da queste grammatiche si diconolinguaggi dipendenti da contesto

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 3 / 37

Page 4: PumpLemma he e Derivazioni

Linguaggi Contestuali Linguaggi Monotoni

Non tutti i linguaggi possono essere generati attraverso grammatichedipendenti da contesto

Esempio.Consideriamo grammatiche aventi, tra le altre, produzioni del tipo:�

1. AB → CDEF2. CB → BC

che evidentemente non sono produzioni contestuali

Osservazione. Tali produzioni non hanno parti destre di lunghezzanon inferiori a quelle delle parti sinistre.

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 4 / 37

Page 5: PumpLemma he e Derivazioni

Linguaggi Contestuali Linguaggi Monotoni

Grammatiche e Linguaggi Monotoni

Una grammatica G = (X ,V ,S,P) è monotòna quando ogni suaproduzione è monotona:

∀(v → w) ∈ P : |v | ≤ |w |

Un linguaggio è monotòno quando esiste una grammatica monotonache lo genera.

Su alcuni testi queste definizioni vengono date per le grammatichedipendenti da contestovi è uno stretto legame a livello di queste classi di linguaggi

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 5 / 37

Page 6: PumpLemma he e Derivazioni

Linguaggi Contestuali Linguaggi Monotoni

Esempio (continua).Le produzioni monotone ma non contestuali viste in precedenza:�

1. AB → CDEF2. CB → BC

possono essere sostituite con le seguenti catene di produzionicontestuali:

AB→ CDEF equivale a

AB → AGAG → CGCG → CDEF

CB→ BC equivale a

CB → XBXB → XCXC → BC

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 6 / 37

Page 7: PumpLemma he e Derivazioni

Linguaggi Contestuali Teoremi di Equivalenza sui Linguaggi Monotoni

Teoremi di Equivalenza

Teorema. Sia G una grammatica monotona, tranne al piú per unaproduzione S→ λ.Se S non appare in una parte destra di produzioni di G, allora esisteuna grammatica contestuale G′ che risulta equivalente a G

In maniera equivalente si dimostra:

Teorema. Un linguaggio L è contestuale sse esiste una grammatica Gtale che L = L(G) a produzioni monotone, tranne al piú il caso cheλ ∈ L per cui puó essere generato direttamente da S se S non apparein alcuna parte destra di produzioni di G

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 7 / 37

Page 8: PumpLemma he e Derivazioni

Linguaggi Contestuali Teoremi di Equivalenza sui Linguaggi Monotoni

Dim. Supponiamo che le produzioni possano essere ricondotte a:

A1A2 . . .Am→ B1B2 . . .Bn

con m ≤ n e Ai ∈ V , i = 1, . . . ,mUsiamo m nuovi simboli non terminali Ck 6∈ V , k = 1, . . . ,mTrasformiamo ogni produzione nella seguente maniera:

A1A2 . . .Am → C1A2 . . .Am

C1A2 . . .Am → C1C2A3 . . .Am...

C1C2 . . .Cm−1Am → C1C2 . . .CmBm+1Bm+2 . . .Bn

C1C2 . . .CmBm+1Bm+2 . . .Bn → C1C2 . . .Cm−1BmBm+1 . . .Bn...

C1B2 . . .Bn → B1B2 . . .Bn

G′ è contestuale e si dimostra: L(G) = L(G′)N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 8 / 37

Page 9: PumpLemma he e Derivazioni

Linguaggi Contestuali Teoremi di Equivalenza sui Linguaggi Monotoni

Esempio. Consideriamo il linguaggio: L = {anbncn | n > 0}

produzioni di una possibilegrammatica monotona per L:

S → aSBC | aBCCB → BCaB → abbB → bbbC → bccC → cc

. . . trasformandole in produzionicontestuali equivalenti:

 

S → aSBC | aBCCB → XBXB → XCXC → BCaB → abbB → bbbC → bccC → cc

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 9 / 37

Page 10: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto

Grammatiche e Linguaggi Liberi da Contesto

Una grammatica G = (X ,V ,S,P) è una grammatica libera dacontesto sse le sue produzioni sono tutte del tipo:

A→ w con A ∈ V

Il linguaggio L(G) si dice linguaggio libero da contesto

nome: in una derivazione, ogni non terminale può esseresostituito con una parte destra di una sua produzione,indipendentemente dal contesto della forma di frase in cui si trovasostituzione sempre validaappartiene a questa categoria la maggior parte dei linguaggi diprogrammazione

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 10 / 37

Page 11: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto

Osservazioni.La classe dei linguaggi liberi è inclusa in quella dei linguaggicontestuali

linguaggi contestuali linguaggi liberi

Si può ottenere un linguaggio libero considerando produzioni doveil contesto destro e quello sinistro siano vuoti (= λ)Eccezione una grammatica libera ammette ogni tipo di λ-regolaossia ogni produzione del tipo

A→ λ con A 6= S

vietate dalle grammatiche contestuali

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 11 / 37

Page 12: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Alberi di Derivazione e Derivazioni Canoniche

Alberi

Le derivazioni di una grammatica libera possono essere rappresentategraficamente da alberi

Albero: grafo orientato, aciclico, connesso con al più un arco entranteper ogni nodo

la frontiera dell’albero èrappresentata dalle foglie lette dasinistra verso destrala lunghezza di un cammino dallaradice ad una foglia è data dalnumero di non terminali incontratil’altezza dell’albero è data dallalunghezza del cammino più lungo

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 12 / 37

Page 13: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Alberi di Derivazione e Derivazioni Canoniche

Alberi di Derivazione

Data G = (X ,V ,S,P) libera e w ∈ X∗ tale che S∗⇒ w , un albero di

derivazione di w , denotato, Tw è così formato:1 radice← S2 nodi interni← simboli di V3 foglie← simboli di X ∪ {λ}4 se esiste la prod. A→ A1A2 · · ·Ak in P allora un nodo interno è A

può essere padre dei nodi figli A1,A2, . . . ,Ak

5 w si deve ottenere da Tw leggendo le foglie da sinistra a destra

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 13 / 37

Page 14: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Alberi di Derivazione e Derivazioni Canoniche

Osservazioni.Un albero di derivazione non impone alcun criterio di scelta del nonterminale da espandere tramite una sua regola di produzione perottenere la sequenza corrispondente ad una derivazione

data una derivazioneesiste uno ed un solo albero che la rappresentadato un albero di derivazioneesistono più derivazioni possibilia seconda dell’ordine scelto per l’applicazione delle produzioni

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 14 / 37

Page 15: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Alberi di Derivazione e Derivazioni Canoniche

Esempio. Data una grammatica libera G = ({a},{S,H},S,P) con

P = {S1→ Ha, H

2→ HS, H3→ a}

La stringa aaaa ∈ L(G) si deriva sia tramite:

S⇒1

Ha⇒2

HSa⇒3

aSa⇒1

aHaa⇒3

aaaa

sia con:S⇒

1Ha⇒

2HSa⇒

1HHaa⇒

3Haaa⇒

3aaaa

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 15 / 37

Page 16: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Alberi di Derivazione e Derivazioni Canoniche

Derivazioni Canoniche

Data una grammatica G = (X ,V ,S,P) si dirà che la derivazione

S⇒ w1⇒ w2⇒ · · · ⇒ wn = w

dove wi = yiAzi e wi+1 = yiwizi , con i = 1, . . . ,n− 1

è una derivazione canonica destra (risp. canonica sinistra)sse per ogni i = 1, . . . ,n− 1 risulta:

zi ∈ X∗ (risp. yi ∈ X∗)

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 16 / 37

Page 17: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Alberi di Derivazione e Derivazioni Canoniche

Esempio.Considero la grammatica con produzioni:

P =

S → 0B | 1AA→ 0 | 0S | 1AAB → 1 | 1S | 0BB

Derivazione sinistra di 0011:

S⇒ 0B⇒ 00BB⇒ 001B⇒ 0011

Derivazione destra di 0011:

S⇒ 0B⇒ 00BB⇒ 00B1⇒ 0011

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 17 / 37

Page 18: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Principio di sostituzione

S∗⇒ 0011 S

∗⇒ 000111

Iterando:

0011 |w | = 4000111 |w | = 6

00001111 |w | = 8...

...00n11n |w | = 2n + 2

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 18 / 37

Page 19: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Principio di sostituzione

Osservazioni.Alberi di derivazione si possono sostituire con sottoalberi alberi dipari radice (non terminale)Generalizzazione: supposto di incontrare almeno due volte unnon terminale A nell’albero di derivazione di z

il sottoalbero più basso con radice A genera wquello più alto genera vwxsostituendo l’albero più alto con il più basso si ottiene unaderivazione valida della stringa uwyinvece, sostituendo quello più basso con quello più alto si ottieneuna derivazione della stringa uvvwxxy cioè uv2wx2yiterando questa sostituzione si ottiene l’insieme

{uvnwxny | n ≥ 0}

La lunghezza delle parole così ottenute cresce in manieracostante (linearmente)Un linguaggio con parole che crescono in modo esponenziale nonpuò essere libero

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 19 / 37

Page 20: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Principio di sostituzione

A

v

A

S

yxwu

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 20 / 37

Page 21: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Principio di sostituzione

Proposizione. Ogni linguaggio libero infinito deve contenere almenoun sottinsieme infinito di stringhe della forma

uvnwxny n ≥ 0

Il fattore di ramificazione massimo per una grammatica liberaG = (X ,V ,S,P) è dato da:

max{|w | ∈ N | A→ w ∈ P}

Lemma. Data una grammatica libera G = (X ,V ,S,P), supponiamoche il fattore di ramificazione sia m.Sia Tw un albero di derivazione per una stringa w di L(G).Se l’altezza di Tw è al più pari a j ∈ N, allora |w | ≤ mj

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 21 / 37

Page 22: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Principio di sostituzione

Dim. Per induzione sull’altezza j dell’albero di Tw :base j = 1 : |w | ≤ m = m1

passo si suppone che il lemma valga per alberi di altezza pari al più aj (radice = non terminale), si deve dimostrare anche per j + 1:

Sia A→ v , dove v = v1v2 · · · vk , |v | = k , k ≤ m

la prod. che determina il livello più alto dell’albero

Ogni simbolo vi ∈ v , i = 1, . . . , k può essere radice disottoalberi di altezza al più uguale a j , essendo Tw in questocaso di altezza j + 1

Per ipotesi, questi sottoalberi hanno al più mj foglie.

Poiché |v | = k ≤ m, per la stringa w , frontiera di Tw , risulterà:

|w | ≤

k volte︷ ︸︸ ︷

mj + mj + · · ·+ mj= |v | ·mj = k ·mj ≤ m ·mj = mj+1

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 22 / 37

Page 23: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Pumping Lemma per Linguaggi Liberi

Pumping Lemma per Linguaggi Liberi

Teorema uvwxy.Sia L un linguaggio libero da contesto.Esiste una costante p, dipendente solo da L, tale chese z ∈ L tale che |z| > p,allora z può essere scritta come uvwxy in modo che:

1 |vwx | ≤ p2 al più uno tra v e x è la parola vuota (vx 6= λ)3 ∀i ∈ N : uv iwx iy ∈ L

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 23 / 37

Page 24: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Pumping Lemma per Linguaggi Liberi

Dim. (schema)Sia G una grammatica che genera LSiano m = max{|v | | A→ v ∈ P} e k = |V |

Posto p = mk+1, consideriamo z ∈ L tale che |z| > p

Per il lemma: |z| > p = mk+1 allora ogni albero di derivazione per z haun’altezza maggiore di k + 1.

k = |V | implica che in un cammino dell’albero ci sia una multiplaoccorrenza di un NT.

Sia A ∈ V quello che compare nella occorrenza più in alto ossia non visono altri NT ripetuti prima dell’A superiore:il cammino dalla A superiore ad una foglia ha lunghezza al più k + 1

Chiamiamo vwx la stringa derivata dal sottoalbero radicato nella Asuperiore, dove w è la sottostringa derivata dall’occorrenza inferiore

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 24 / 37

Page 25: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Pumping Lemma per Linguaggi Liberi

1 Dal Lemma risulta: |vwx | ≤ mk+1 = p2 Per assurdo se fosse v = λ = x la sostituzione dell’albero radicato

nell’A superiore con quello inferiore non provoca nessuncambiamento.Ma in tal caso esiste un cammino di lunghezza inferiore.Si ottiene un albero di derivazione di z di altezza al più pari ak + 1. Assurdo.

3 Applicando il principio di sostituzione a z = uvwxysostituiamo il sottoalbero radicato nell’occorrenza inferiore di Acon quello dell’occorrenza superiore ottenendo:

uwy = uv0wx0y

Con la sostituzione inversa: uv2wx2y e ripetendo i − 1 volte:

uv iwx iy

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 25 / 37

Page 26: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Pumping Lemma per Linguaggi Liberi

Osservazioni.Dato un linguaggio generato da una grammatica non libera non sipuò escludere che esista una grammatica libera che lo generiSe un linguaggio infinito non rispetta il Pumping Lemma deilinguaggi liberi non può essere generato da una grammatica liberaQuindi questo teorema fornisce una condizione necessaria manon sufficiente perché un linguaggio sia liberoSi utilizza per dimostrare che un linguaggio non sia libero

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 26 / 37

Page 27: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Ambiguità

Ambiguità

Una grammatica G libera da contesto si dice ambigua sse esiste unastringa x in L(G) che ha due alberi di derivazione differenti ovvero ssex ha due derivazioni sinistre (o destre)

Esempio.La grammatica libera G = (X ,V ,S,P) conX = {a,+}, V = {S} e P = {S→ S + S, S→ a}è ambigua. Ad es. w = a + a + a ottenibile mediante 2 alberi:

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 27 / 37

Page 28: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Ambiguità

Esempio.Grammatica per l’assegnazione:

<assegnazione>→ <id> = <espressione><id>→ A | B | C<espressione>→ <espressione> + <espressione> |

<espressione> * <espressione> |(<espressione>) | <id>

Dimostrare che è ambigua.

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 28 / 37

Page 29: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Ambiguità

Esempio. G = (X ,V ,S,P) con X = {if,else,(,),a,b,p,q}V = {S,C} P = { S→ if C S else S | if C S | a | b,

C → (p) | (q) }Si consideri la stringa if (p) if (q) a else b

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 29 / 37

Page 30: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Ambiguità

Per ottenere G′ = (X ,V ′,S,P′) non ambigua usiamo la convenzionedi associare ogni else alla if più vicina:V ′ = V ∪ {S1,S2}

P′ =

S → S1 | S2S1 → if C S1 else S1 | a | bS2 → if C S | if C S1 else S2 | a | bC → (p) | (q)

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 30 / 37

Page 31: PumpLemma he e Derivazioni

Linguaggi Liberi da Contesto Ambiguità

Linguaggi Inerentemente Ambigui

Un linguaggio G si dice inerentemente ambiguo sseogni grammatica che lo genera è ambigua

Esempio.L = {aibjck | i , j , k > 0, (i = j)∨ (j = k)}

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 31 / 37

Page 32: PumpLemma he e Derivazioni

Esercizi

Esercizi.

Dimostrare che i seguenti linguaggi non sono liberi da contesto:L = {at | t primo}L = {anbncn | n > 0}L = {an2 | n ≥ 0}L = {aibj | i = 2j , i , j ≥ 0}L = {akbr | k > 0, r > k2}

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 32 / 37

Page 33: PumpLemma he e Derivazioni

Esercizi Esercizio 2

Esercizio 2. Dimostrare che L = {anbncn|n > 0} non è liberoSupponiamo (per assurdo) che L sia libero.Allora vale il Pumping Lemma per un certo p ∈ N fissato.Si consideri la parola z = uvwxy = apbpcp ∈ L: |z| = 3p > p.Per il P.L. deve essere |vwx | ≤ p.Per la composizione di vwx si hanno le seguenti possibilità:

1 ripetizioni di un solo simbolo:ak , bk o ck con k > 0

2 a cavallo tra ripetizioni di due simboli:ahbk o bhck con h, k > 0

3 vwx è del tipo ahbpck ,ma in tal caso si vede subito che |vwx | > p: assurdo

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 33 / 37

Page 34: PumpLemma he e Derivazioni

Esercizi Esercizio 2

In tutti questi casi si può dimostrare che uv2wx2y 6∈ Lquindi L non può essere libero.

(caso 1.)vwx = ak , 0 < k ≤ paggiungendo almeno a ed al più ap si ottiene:

uv2wx2y = ap+kbpcp

vwx = bk , 0 < k ≤ p analogamentevwx = ck , 0 < k ≤ p analogamente

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 34 / 37

Page 35: PumpLemma he e Derivazioni

Esercizi Esercizio 2

(caso 2.)vwx = akbr , 0 < k + r ≤ p per la 2. del Pumping Lemma:

1 v 6= λ, x 6= λ:se v 6= λ allora v = ak ′ perchè se fosse v = ak br ′ allora

uv2wx2y = ap−k ak br ′ak br ′bscp 6∈ L

con p ≤ s ≤ 2(r − r ′) + p− rAnalogamente x 6= λ implica che x = br ′ per cui:

uv2wx2y = ap+k ′bp+r ′cp 6∈ L

per k ′, r ′ > 02 v 6= λ, x = λ

per le considerazioni fatte: v = ak ′ , 0 < k ′ ≤ k per cui

uv2wx2y = ap+k ′bpcp 6∈ L

3 v = λ, x 6= λ: analogamente al sottocaso precedentevwx = bkcr , 0 < k + r ≤ p caso analogo al precedente

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 35 / 37

Page 36: PumpLemma he e Derivazioni

Esercizi Esercizio 3

Esercizio 3. Dimostrare che L = {an2 | n ≥ 0} non è libero

Consideriamo L = {λ,a,aaaa,a9,a16, . . .} e supponiamo sia libero.Vale il Pumping Lemma per un certo p ∈ N.Considero allora z = uvwxy = ap2 ∈ L tale che |z| = p2 > pAnche uv2wx2y ∈ L (per la 3. del Lemma)Ma si osservi l catena di maggiorazioni:|uv2wx2y | = |uvwxy |+|vx | = |z|+|vx | ≤ p2+p < p2+2p+1 = (p+1)2

rissumendo: |uv2wx2y | < (p + 1)2

Inoltre |uv2wx2y | = |z|+ |vx | > |z| = p2

Perciò z ha una lunghezza compresa (non uguale) tra due quadratisuccessivi, ciò implica che uv2wx2y 6∈ L.Assurdo, quindi L non è libero

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 36 / 37

Page 37: PumpLemma he e Derivazioni

Esercizi Esercizio 1

Esercizio 1. Dimostrare che L = {at | t primo} non è liberoSupponiamo che L sia libero. Allora vale il pumping lemmaper cui considerato un certo p,sia z ∈ L e |z| = t > p con t primo e z = uvwxyPoniamo

k = |vx | > 0 quindi k + 1 > 1r = |uwy | = t − k

Consideriate le stringhe zi = uv iwx iy ∈ L ∀i ≥ 0 risulta:

|zi | = |uv iwx iy | = |uwy |+ i |vx | = r + ik

Allora deve valere anche per la lunghezza di zt+1 ∈ L:

|zt+1| = r + (t + 1)k = r + tk + k = tk + t = (k + 1)t

Essendo un multiplo proprio di un numero primoquesta lunghezza non può essere un numero primo,quindi la stringa non è nel linguaggio: zt+1 /∈ L (assurdo)

N. Fanizzi (LdP) Linguaggi Contestuali e Liberi 18 marzo 2010 37 / 37