Linguaggi regolari - Carlo Toffalori Flavio Corradini Stefano Leonesi Stefano Mancini. Teoria d

Diamo anzitutto un esempio di linguaggio regolare.

Esempio. Consideriamo l'alfabeto {a, b} e in esso il linguaggio L = {a" brn I n,m E N, n, n-i > 1} .

Allora L è regolare, perchè si verifica facilmente che L è generato dalla gramma-tica di tipo 3 G = (N, T, P, S) dove N = {S, B}, T = {a, b} e P è l'insieme di produzioni dato da:

S --> aS i aB

B hB I .

Quanto ai linguaggi non regolari, c'è un risultato fondamentale noto come Teore-ma uvw, o Pumping Lemma (quest'ultima denominazione inglese è ormai invalsa anche nell'uso italiano) che stabilisce una condizione che un linguaggio regolare deve necessariamente soddisfare, e dunque esclude dai linguaggi regolari tutti quelli incapaci di rispettarla.

Teorema uvw (Pumping Lemma per Linguaggi Regolari) 5.6.1 Sia L un lin-guaggio di tipo 3 su un alfabeto T. Esiste una costante n E N (dipendente da L) tale che, per ogni z E L, se 1(z) > n, allora ci sono stringhe u, v, w E

r

^{per cui}

valgono le seguenti proprietà:

(a) z = uvw;

(b) O < 1(v) < n;

(c) Vi

E N, uvi w E L.

Dimostrazione. Sia G = (N, T, P, S) una grammatica regolare che genera L, cioè L = L(G). Sia poi n la cardinalità di N, cioè il numero di simboli non terminali della grammatica. Dalla definizione di L(G), segue che la stringa z appartiene a L se e solo se z è derivabile in G dal simbolo iniziale (S z) e cioè se e solo se esiste una sequenza di stringhe 2/0, w 1 , . . . , wn, tali che S = wo, z = wm, e, per ogni i = 1, , m, wi è derivabile direttamente da wi_i in G

S WO -4 G W1... ->G Wi G • .. ->G Wm = Z.

Dalla definizione di linguaggio regolare segue poi che ogni v4 deve essere del tipo wi = w2Ai per qualche stringa di simboli terminali u E T* e per qualche simbolo non terminale Ai E N; in particolare di è un prefisso proprio di di+ , e quindi di tutte le stringhe '4 per k > i. Infatti le produzioni di G che generano , wrn, da S sono della forma A > aB oppure A a con A, B E N e a E T. Per lo stesso motivo abbiamo che, se vale l'ipotesi 1(z) > n, allora m > n; di conseguenza, siccome n è il numero totale dei simboli non terminali e m > n, deve esistere almeno un simbolo non terminale A che si ripete nella

precedente rappresentazione delle stringhe tit h . . wm . Siano i < k < m gli indici minimi per cui si osserva questa ripetizione

S = wp >G Wi.. . -->G wiA -3G ... G . . . >G Wrn = ^Z.

Consideriamo le stringhe di , wk' e z. Siccome wif è un prefisso proprio di

dk

wk' è un prefisso di z abbiamo che

'4 =

^{di p}^e^{z = wk a}per opportune stringhe p e a in T* (e per a eventualmente vuota). A questo punto poniamo u = u,, v = p e w = o- . E' facile convincersi che u, v e w così definiti soddisfano le condizioni

(a), (b) e

(e)

del teorema.

❑

Ribadiamo che il Teorema uvw fornisce soltanto una condizione necessaria per-ché un linguaggio sia regolare. Esso non può essere quindi utilizzato per mostrare la regolarità di un linguaggio, ma semmai per escludere che un linguaggio sia regolare, come il seguente esempio mostra.

Esempio.

Il linguaggio

L = {dei E N, i > 1}

non è regolare. Supponiamo infatti che lo sia. Applicando il Teorema uvw tro-viamo n E N tale che, Vz E L, se 1(z) > n allora

z

= uvw con 0 < 1(v) < n e uv i w E L per ogni naturale i. Prendiamo dunque la stringa z = anbn. Ovviamen-te z E L e 1(z) = 2n > n e quindi esistono stringhe u, v e w come descritte dal teorema; in particolare 0 < 1(v) < n. A questo punto distinguiamo 3 possibilità:

1. v contiene solo simboli a, 2. v contiene solo simboli b, 3. v contiene tanto a quanto b.

In tutti e tre i casi, si osserva facilmente che uv 2 w ¢ L e cioè che uv 2 w non si può scrivere come al bi per nessun naturale i. Ricordiamo infatti che uvw sta in ^L e quindi si può esprimere in questa forma. Ma allora l'immissione di un'ulteriore sottostringa non vuota v produce

1. più a che b, 2. più b che a,

3. alternanze di a, b e ancora a

e quindi situazioni incompatibili con L.

Altre applicazioni del Teorema uvw rivelano importanti proprietà di decidibilità dei linguaggi regolari. Discutiamone una.

Proposizione 5.6.2

Siano G una grammatica di tipo 3, L = L(G) il corrispon-dente linguaggio regolare. Sia poi n il numero dei simboli non terminali di G e cioè la costante associata dal Teorema uvw a L. Allora

(a) L non è vuoto se e solo se G genera una stringa z di lunghezza < n.

iil

(b) L è infinito se e solo se G genera una stringa z tale che n < 1(z) < 2n.

Come vedremo nel prossimo paragrafo, la proposizione si può estendere oppor-tunamente anche alle grammatiche e ai linguaggi liberi dal contesto. Ne presen-tiamo comunque la dimostrazione nel caso regolare, per illustrarvi il ruolo del Teorema uvw.

Dimostrazione. (a) È chiaro che, se G genera qualche stringa z, allora, a pre-scindere dalla lunghezza di z, L = L(G) non è vuoto. Viceversa assumiamo che L non sia vuoto ma che tutte le stringhe di L abbiano lunghezza > n. Sia poi z una stringa di lunghezza minima in L. Poiché 1(z) > n, per il Teorema uvw esistono stringhe u, v e w tale che z = uvw, O < 1(v) < n e, per ogni naturale i, uvw E L. In particolare uv t3 w = uw E L; ma uw ha lunghezza inferiore a z = uvw, e questo contraddice la scelta di z. Allora L, quando non è vuoto, deve contenere stringhe di lunghezza < n.

(b) Supponiamo dapprima che G generi una stringa z tale che n < 1(z) < 2n.

Per il Teorema uvw ci sono u, v, w nell'alfabeto T dei simboli terminali di G tali che z = uvw, v a e ogni stringa uvw (per i naturale) è in L. Ovviamente uv i w uviw per i j. Dunque L ha infiniti elementi. Viceversa, assumiamo L infinito. Siccome il numero delle stringhe di fissata lunghezza su T è comunque finito, L contiene elementi di lunghezza arbitrariamente grande. Sia in particolare z una stringa in L di lunghezza minima tra quelle di lunghezza > n. Se 1(z) < 2n allora abbiamo la stringa che stiamo cercando. Altrimenti applichiamo il Teorema uvw a z come nel caso precedente e troviamo u, v e w in T1/4. con O < 1(v) < n, z = uvw e uvi w E L per ogni naturale i. In particolare uw E L; inoltre /(uw) >

n perché 1(z) > 2n e 1(v) < n; finalmente /(uw) < 1(z) perché / (v) > O. Ma

così si contraddice la scelta di z. ^❑

Come già osservato nel corso della precedente dimostrazione, le stringhe di r di una prefissata lunghezza 1 sono in numero finito, e dunque si possono enumerare e decidere effettivamente. Lo stesso vale ovviamente anche per stringhe di lun-ghezza < 1, o compresa tra 1 e 21, per ogni 1. Consideriamo allora i problemi di decidere, per ogni grammatica regolare G,

(a) se L(G) è vuoto o no, (b) se L(G) è finito o no.

In entrambi i casi, una strategia di soluzione consiste nel calcolare anzitutto il numero n dei simboli non terminali di G e poi, se T denota l'alfabeto dei simboli terminali di G, considerare una per una

(a) le stringhe z E T* con 1(z) < n,

(b) le stringhe z E T* con n < 1(z) < 2n

cercando di stabilire, per ognuna di esse, se z è o non è in L(G). Se l'esame dà esito positivo almeno una volta, allora

(a) L(G) 0,

(b)

L(G)

è infinito,

Nel documento Carlo Toffalori Flavio Corradini Stefano Leonesi Stefano Mancini. Teoria della computabilità e della complessità. McGraw-Hill (pagine 89-92)