Costruzione di espressioni regolari 4Indicando con d uno dei possibili digits {0, 1, 2,…,9} --possiamo esprimere il sotto linguaggio dei digits come d = (0 + 1 + 2 + .. + 9)

Quale linguaggio produce l’espressione:(+ + - + %) d d* ?

Ricordando che d+ = dd* il linguaggio prodotto è+ d+ + - d+ + d+

Ovvero il linguaggio degli interi con o senza segno (ad es. +124, -45, 78)

Esercizio: rappresentare con un’espressione regolare il linguaggio delle costanti invirgola mobile con segno.

(+ + - + %) (d+ . d* + . d+) (% + E (+ + - + %) d+ )

Notare la differenza tra +, simbolo dell’alfabeto del linguaggio definitodall’espressione regoalre, e +, simbolo del metalinguaggio delle espressioni regolari

Espressioni regolari e grammatiche regolari

I linguaggi definiti tramite espressioni regolari sono regolari

Espressioni regolari Linguaggi& !a { a }

( s + t) L(s) " L(t)

(s · t) L(s) · L(t) s* ( L( s ) )*

Espressioni regolari e automi

Un linguaggio definito da un’espressione regolare R è definito anche da un automa a stati finiti A, cioè L( R) = L(A).

!

a

linguaggio {!}

linguaggio vuoto &

Linguaggio { a }

Caratteristiche dell’automa :

1. Un unico stato finale2. Nessun arco entrante nel nodo iniziale3. Nessun arco uscente dallo stato finale

Espressioni regolari e automi

L( E1 ) " L( E2 ) !

!

!

!

E1

E2

E2E1!

L( E1 ) • L( E2 )

(L( E ))*E! !

!

!

Esempio

EX: Conversione dell’espressione ( 0 +1 )* 1 ( 0 +1)

00! !

!1

!1

1! !

!1

!

0

!

!

! !

!1

!

0

!!

!

Dall’espressione regolare alle grammatiche regolari

Esempio: Si consideri l’espressione regolare (b* + (ab)*)

3. Si aggiunge l’assioma S che indirizza alla prima e alla seconda grammatica S ) S1 | S2

2. Si individua una grammatica per (ab)* nel seguente modo, dapprima si determina unagrammatica per {ab}

S2 ) a B2 B2 ) b

1. Si individua una grammatica per b* S1 ) bS1 | !

E quindi: S ) S1 | S2 S1 ) bS1 | ! S2 ) a B2 | ! B2 ) b S2 | b

Si aggiungono quindi S2 ) ! B2 )b S2

per ottenere la chiusura riflessiva e transitiva (ab)*

Verifica della regolarità

Teorema: Un linguaggio è regolare se e solo se è accettato da un automa a stati finiti

Ci sono due proprietà che sono a comune dei linguaggi regolari1. La fine di una scansione di una stringa da sinistra a destra deve essere

determinata dalla struttura del linguaggio piuttosto che dalla stringa stessa.Ad esempio possiamo aspettarci che il linguaggio {an bn n *0} non è regolare perchè non sappiamo precisare il limite tra gli a e i b non avendo adisposizione un contatore.

2. I linguaggi regolari sono rappresentati da automi con cicli che mettonoin luce strutture ripetive. Ad esempio mentre il linguaggio {an} ècertamente regolare, il linguaggio {an : n *1 è un numero primo} non lo èin quanto non esiste una periodicità nella sequenza dei primi.

Sebbene ci siano vari strumenti per verificare se un linguaggio è regolare. Es. Valutare tutte le possibili trasformazioni tra i vari schemi (automi, espressioni regolari atc.). Più difficile è verificare se un linguaggio è non regolare.

Esempio di sottostruttura

Il ciclo q1 ) aabab ) q1 può essere fatto un numeroarbitrario di volte, anche zero volte !

b aabab ab

b aabab aabab aabab ab

…..

Pumping Lemma

Dato un linguaggio regolare L è sempre possibile trovare una costante n , 1 per la quale ogni

stringa w $ L con | w | , n sia esprimibile come w = x y z tale che y - !, | x y | . n, ex yi z $ L per i ,0 . In altre parole la stringa che genera il ciclo può essere rimossa o ripetuta indefinitivamente

Supponiamo di avere un’automa A con n stati, applicato ad una una stringa w di lunghezza n.Un’automa A con n stati per leggere una stringa di lunghezza n ha bisogno di n+1 configurazioni

(q0, w1,w2, …wn) |/ (q1, w2,w3, …wn ) |/ …. |/ (qn, !)

Per il principio della piccionaia ci deve allora essere un i e un j con 0 . i < j . n tale che qi = qjcioè la computazione ha almeno un ciclo.

q0 qi

x zy

Si osservi come la parte x della stringa può esserevuota, così come la parte z, mentre la parte y nonpuò essere vuota essendo i < j in senso stretto.

Conseguenze del Pumping Lemma

1. Il linguaggio L = {am bm : m , 0} non è un linguaggio regolare

2. Il Linguaggio L = {ai | i numero primo} non è regolare

Supposto di applicare il Pumping Lemma per qualche intero n si considera la stringa an bn $ L. Questa si dovrebbe riscrivere come w = x y z con

| x y | . n e y - ! ovvero y = ai per qualche i, 0,

ne deriva che x z = a n-i bn ( L

Si considera la decomposizione an = x y z per l’ipotesi del Lemma anchew = x yn+1 z $ L con | w | numero primo.

3. Si dimostri che il linguaggio L = {z$ {a,b }* : |z | è un quadrato perfetto } non è regolare

Es: a a a b b bx= a, y= aa, z =bbbx= aaa, y=b, z=bbx=aa, y=ab, z=bb

| w | = | x yn+1 z | = | x y z yn | = | x y z | + | yn | =n + n | y | = n (1 + | y |)

pertanto considerato che y - ! la lunghezza della stringa w , non è un numero primo

Verifica se un Linguaggio Regolare è vuoto

Se si suppone di usare la rappresentazione del linguaggio nella sua forma di automaa stati finiti il problema puo’ essere formulato nel modo seguente:

• Se esiste un cammino dallo stato S ad uno stato accettante ! Z allora il linguaggio non è vuoto

• Se non esiste una cammino dallo stato iniziale a qualche stato accettante ! Z il linguaggio è vuoto

• Se esiste una cammino dallo stato iniziale S ad un qualche stato accettante ! Z e che attraversa almeno due volte uno stesso stato il linguaggio è infinito

Equivalenza di linguaggi regolari

E’ conveniente mettere due descrittori di linguaggi regolari sotto forma di automa a statifiniti deterministici in modo da favorirne il confronto.

Verifica dell’equivalenza di stati

Due stati p e q con p " q si dicono equivalenti (e quindi sostituibili da un unico stato che si comporti come p e q messi insieme) se:

p e q sono entrambi finali o entrambi non finali, ePer ogni simbolo di input a, presi s = #(p, a) r = #(q, a) s e r sono lo stesso stato o sonoequivalenti.

Due stati non equivalenti si dicono distinguibili, nel qual caso esiste almeno un simbolo diinput che li distingue.

Il confronto verrà fatto trasformando i due automi nella loro forma minimale e, a menodi una ridenominazione degli stati, verificare se i due automi minimali coincidono.

[Questo procedimento funziona in quanto si può dimostrare come la forma minimale di un automa è unico].

Esempio

AG

$AG

0BG

1FE

01CE

BH

$BH

0GG

1CC

NONO NOSI

NO

AE

$AE

1FF

0BH

00GG

01CC

$AE

NO NONO NO NONONO

B equ HA equ E

A dist G

A

F

D

E

B

G H

C0

0

0

00

0

0

1

1

11

1

1

0

1

1

Basta trovare una stringa che renda distinguibili due stati

O essere sicuri che ogni possibilestringa renda equivalente due stati

Algoritmo marca-stati

1. Se p è uno stato accettante e q è uno stato non accettante lacoppia {p,q} è marcata distinguibile [questa eventualità èsegnalata da un flag X]

2. Siano p e q due stati per cui un simbolo di input a ! ! portaa due stati r=#(p,a) e s= #(q,a) che sappiamo esseredistinguibili, allora anche la coppia {p,q} è distinguibile.

Si rappresentano in una matrice triangolare di coordinateq1, q2, …, qn x q0, q1, …, qn-1 tutti i possibili accoppiamenti tra stati q1

q3

q2

q4

q5

q6

q7

q0 q1 q2 q3 q4 q5 q6

X X X X X X X

Supposto essere q7uno stato finale

Praticamente due stati risultano equivalenti se non siamo riusciti a dimostrare la lorodistinguibilità

Esempio di esecuzione

BH

B

DC

EFGH

A B C D E F G

xxxx

xx

x

x

x x

A

F

D

E

B

G H

C0

0

0

00

0

0

1

1

11

1

1

0

1

1

x

x xx x xx x x X x

x x x x

B

DC

EFGH

A B C D E F G

xxxx

xx

x

x

x x

x

x xx x xx x x x x

x x x xStati equivalenti

(A, E) (B, H) (D, F)

(E, A)#(E,0) = H#(A,0) = B#(E,1) = F#(A,1) = F

Si prodece da sinistraverso destra edall’alto verso ilbasso

(G, A)#(G,0) = G#(A,0) = B#(G,1) = E#(A,1) = F

(G, E)#(G,0) = G#(E,0) = H#(G,1) = E#(E,1) = F

Complessità dell’algoritmo marca stati

• L’algoritmo visita ripetutamente la matrice da sinistra verso destra e dall’altoverso il basso. Ogni visita richiede O(n2) passi, dove n è il numero degli stati.

• La visita della matrice deve essere ripetuta perchè la distinguibilità di una coppiadi stati può dipendere dalla distinguibilità di una coppia di stati che la precedenell’ordine di visita, e che non è stata finora decisa.

• Basta ripetere la visita k volte, dove k è la lunghezza del cammino più lungopresente nel grafo, per essere sicuri di aver deciso la distinguibilità di ogni coppiadi stati, visto che la distinguibilità di una coppia si stati si basa su quella dei lorosuccessori.

• In un grafo, la lunghezza del cammino (aciclico) più lungo k è limitatasuperiormente da n, il numero degli stati.

• Quindi se semplicemente ripetiamo la visita n volte, l’algoritmo decide ladistinguibilità di tutte le coppie, con complessità O(n3)

• In realtà la ripetizione della visita per n volte è necessaria solo nel caso peggiore.Si possono fare ottimizzazioni per limitare il numero di ripetizioni a quellestrattamente necessarie, ma la complessità del caso peggiore resta O(n3)