Forma Normale di Chomsky

2. Eliminazione delle produzioni unitarie

Una produzione si dice unitaria se è della forma A ! B. Le produzioni unitarie in pratica consistono in

una ridenominazione di variabili, talvolta necessaria, al momento della creazione della grammatica.

La rimozione di queste regole implica la definizione di altre regole che producano le stesse stringhe.

Es1

A ! aA | a | B

B ! bB | b | C

è evidente la catena di regole che da A porta al simbolo C via il simbolo B

Algoritmo

1. Per ogni simbolo X " VN della grammatica G1 si individuano tutti i simboli non terminali ad esso

collegati raggiungibili da produzioni unitarie, chiamo questa lista CHAIN(X).

2. Le produzioni P2 della grammatica trasformata G2 sono costruite a partire dalle produzioni P1

considerato che la regola X ! w è collocata in P2 se esiste un simbolo Y e una stringa w tale che:

Sia P1 l’insieme delle produzioni della grammatica di partenza G1 (senza #-produzioni).

a) Y " CHAIN(X)

b) Y ! w " P1

c) w $ VN wYX

Forma Normale di Chomsky

Eliminazione delle produzioni unitarie cont.

C ! cC | c

B ! bB | b

A ! aAa | aa | B | CS ! ACA |AC | CA | AA |A |C | "

Es2

Determinazione dei simboli unitari

CHAIN(S) = {S,A,C,B}

CHAIN(A) = {A,B,C}

CHAIN(B) = {B}

CHAIN(C) = {C}

C ! cC | c

B ! bB | b

A ! aAa | aa | B | CS ! ACA |AC | CA | AA |A |C | " S ! ACA |AC | CA | AA | aAa | aa | bB | b |cC | c | "

A ! aAa | aa |

C ! cC | c

B ! bB | b

Esercizio- Scrivere la grammatica equivalente della grammatica G13 E ! E+T | E- T | T

T ! T *F | T/F | F

F ! (E) | id

id ! a | b | c

bB | b | cC | c

Forma Normale di Chomsky

3. Eliminazione dei simboli inutili

Def. In una Grammatica contex-free, un simbolo x ! (VN " VT) è detto simbolo utile se esiste una

derivazione

S #* u x v #* w con u, v ! (VN " VT)* e w ! VT*

Un simbolo che non è utile è detto inutile.

Affinché una variabile sia considerata utile occorre che si verifichino le seguenti due condizioni:

Generabilità - cioé tramite il simbolo si deve poter pervenire ad una stringa di caratteri terminali

(compresa eventualmente la stringa vuota $)

S % AC |BS | B

A % aA| aF

B % CF | b

C % cC | D

D % aD | BD | C

E % aA | BSA

F % bB | b

Raggiungibilità - che il simbolo deve far parte di una forma sentenziale, ovvero è raggiungibile a partire

dal simbolo distinto S

Qual’è il linguaggio generato da questa grammatica?

Forma Normale di Chomsky

3. Eliminazione dei simboli inutili (cont.)

Algoritmo (individuazione dei simboli generatori)

S ! AC |BS | B

A ! aA| aF

B ! CF | b

C ! cC | D

D ! aD | BD | C

E ! aA | BSA

F ! bB | b

- Si collocano nella lista GEN tutti simboli A tali che esiste una regola A ! w in P con w " VT*

Per ogni variabile A " VN se c’é una regola A ! w con w " (PREV # VT)* allora

GEN = GEN # { A}

repeat

PREV := GEN

until GEN= PREV

GEN PREV

{ B,F}

{ B,F}{ B,F, A, S}

{ B,F, A, S}{ B,F, A, S,E}

{ B,F, A, S,E}{ B,F, A, S,E}

La grammatica risultante G’ avrà come VN i simboli in GEN, come produzioni P’ le produzioni A !w di P

tali che A " GEN e w " (GEN # VT)*, come VT i simboli terminali che occorrono nelle parti destre di P’,

ovvero VN = { B,F, A, S,E}, VT = { a,b} e P’ come sopra indicato.

S ! BS | B

A ! aA| aF

B ! b

E ! aA | BSA

F ! bB | b

P’

Forma Normale di Chomsky

3. Eliminazione dei simboli inutili (cont.)

Algoritmo (individuazione dei simboli raggiungibili)

RAGG = simbolo distinto di G

NEW := RAGG-PREV

repeat

PREV :=!

PREV:= RAGG

RAGG PREV

{ S} { !}

S " BS | B

A " aA| aF

B " b

E " aA | BSA

F " bB | b

per ogni variabile A # NEW

per ogni regola A " w addiziona tutte le variabili in w a RAGG

until RAGG=PREV

NEW

{ S}{ S, B} { S}

{ B}{ S, B}{ S, B}

La grammatica risultante G’ avrà come VN i simboli in RAGG, come produzioni P’ le produzioni A "w di

P tali che A # RAGG e w # (RAGG $ VT)*, come VT i simboli terminali che occorrono nelle parti destre

di P’, ovvero VN = { S,B}, VT = {b} e P’ come sopra indicato.

P’

S " BS | B

B " b

Forma Normale di Chomsky

Una grammatica G si dice in forma normale (di Chomsky) se ciascuna regola è della forma:

1. A ! BC con B, C ! VN - { S}

2. A ! a

3. S ! "

Data una grammatica di tipo 2, G = < VN,VT,P, S > è possibile costruire per via algoritmica una

grammatica G’ = < V’N,VT,P’, S > in forma normale (di Chomsky).

Si assume che la grammatica abbia la seguente struttura:

• Il simbolo distinto S non è ricorsivo

• G è privo di !-produzioni ad esclusione di S ! !

• G non contiene produzioni unitarie

• G non contiene simboli inutili

Una produzione di una tale grammatica può avere solo una delle seguenti forme:

S ! !

A ! a a ! VT

A ! w w !( ( VN # VT ) - { S})* e | w | > 1

Si osservi come avendo eliminato le produzioni unitarie la parte destra di una regola non potrà essere

formata dal un solo simbolo non terminale, pertanto le regole A ! w avranno come parte destra più

simboli terminali e non terminali.

Forma Normale di Chomsky

Si tratta in definitiva di vedere come si trattano le produzioni A ! w in cui | w | > 1.

Il primo passo sarà quello di sostituire i terminali presenti in w con opportuni simboli non terminali.

S ! aABC | a

A ! aA | a

B ! bcB | bc

C ! cC | c

S ! A’ABC | a

A ! A’A | a

B ! B’C’B | B’C’

C ! C’C | c

A’ ! a

B’ !b

C’ !c

A questo punto dobbiamo gestire le regole con parti destre costituite da più di due simboli non

terminali, in quanto tutte le altre soddisfano già le condizioni della forma normale.

Ciò viene fatto introducendo delle ulteriori variabili.

produzioni già in forma normale

produzioni ancora non in forma normale

Forma Normale di Chomsky

non in forma normaleS ! A’ABC | a

A ! A’A | a

B ! B’C’B | B’C’

C ! C’C | c

A’ ! a

B’ !b

C’ !c

non in forma normale

Si introducono altre opportune variabili

S ! A’ABC S ! A’T1

T1 ! ABC

S ! A’T1

T1 ! A T2

T2 ! BC

B ! B’C’B B ! B’T4

T4 ! C’B

S ! A’T1 | a

A’ ! a

T1 ! A T2

T2 ! BC

A ! A’A | a

B ! B’T4 | B’C’

T4 ! C’B

C ! C’C | c

B’ !b

C’ !c

Si ha pertanto che la grammatica di partenza

S ! aABC | a

A ! aA | a

B ! bcB | bc

C ! cC | c

viene trasformata in

Forma Normale di Chomsky

E $ E+T | E- T | T

T $ T *F | T/F | F

F $ (E) | id

id $ a | b | c

Esercizio

Trasformare in forma normale di Chomsky la grammatica:

Automi Pushdown

Rappresentano una modificazione degli automi a stati finiti in quanto introducono il concetto di memoria, tale memoria è rappresentata sotto forma di stack

La grammatica G14

con regole

S $ a S a | b S b | "

riconosce stringhe palindrome

S%aSa % aa

S%aSa % abSba %abba

S%aSa % abSba %abbaSabba%abbaabba

......

a b b a a b b a

Controllo

b

b

a

input

testina di lettura

stack

Automi Pushdown

Un automa pushdown è definito dalla sestupla < K, ", &, ' , s, Z >

K - Insieme degli stati

" - Alfabeto di Ingresso (Alfabeto terminale)

& - Alfabeto dello stack

s - Stato iniziale s ! K

Z - insieme degli stati finali Z ( K

' - relazione di transizione è un sottoinsieme finito di

# ( K x (" # {"} ) x &*) x (K x&*)

#

Transizioni negli automi pushdown

• Una quintupla (p, a, )), (q, *) rappresenta una transizione e viene interpretata nel

seguente modo :

#

se l’automa si trova in uno stato p, sta leggendo il simbolo a dal nastro, mentre ) si trova

sul top dello stack, l’automa passa allo stato q e rimpiazza ) con * sul top dello stack

Ex:

• la transizione (p, ", )), (q, *) non legge alcun simbolo dal nastro di input

passa dallo stato p allo stato q

mette * al posto di ) nello stack

• la transizione (p, u, "), (q, a) legge il carattere u

## # passa dallo stato p allo stato q

## # effettua il push di a nello stack" "

• la transizione (p, u, a), (q, ") legge il carattere u

## # passa dallo stato p allo stato q

"" " effettua il pop di a dallo stack

Configurazioni negli automi pushdown

• Si definisce una configurazione dell’automa un elemento di

## # #

## # # K x "* x &*

in cui la prima componente è lo stato corrente della macchina, la seconda componente è la

porzione di input che deve essere ancora letta, la terza componente è il contenuto dello stack

Ex: ( q, bba, bba) è una configurazione in cui il contenuto corrente dello stack è

bba (b è al top) e la parte di stringa ancora da leggere è bba

• Date le due configurazioni c1

= (p, x, +) e c2

= (q, y, ,) si dirà che c1

si trasforma in c2

in un singolo passo e si scrive

(p, x, +) |- (q, y, ,) se esiste una transizione

(p, s , )), (q, *) ! ' tale che:

x = sy, + = ). e , = * .a b b a a b b a

Controllo

b

b

a

input

testina di lettura

stack

Ex:

(q, bba, bba) |- (q, ba, ba)

in virtù di una transizione in ' avente la struttura

(q , b, b), (q, ")per cui x= bba y=ba + = bba , = ba

.=ba )=b *= "

Computazioni di un automa pushdown

• Una sequenza di configurazioni

C0

, C1

, ....., Cn

con n > 0

tale che

C0

= ( s , w, !) |" C1

|" C2

|" ....... |" Cn = (p, ! , !)

per qualche p # Z, viene chiamata una computazione accettante di

! lunghezza n.

• Dato un automa pushdown A, il linguaggio accettato da A e denotato da

L(A) è l’insieme delle stringhe accettate da A

Esempio stringhe palindrome 1

Automa per il riconoscimento del linguaggio L = {w c w R}A = < {s,f}, {a,b,c}, {a,b}, !, s, { f } > con ! che contiene le

transizioni:

Stato Stringa di input stack transizione

s abbcbba "

s bbcbba a 1

s bcbba ba 2

s cbba bba 2

f bba bba 3

f ba ba 5

f a a 5

f " " 4

esecuzione per abbcbba1. (( s, a, " ), (s, a)! [ push a]2. (( s b, " ), (s, b) [ push b]3. (( s, c, " ), (f, ")! !

4. (( f a, a ), (f, ")! [ pop a ]

5. (( f, b, b ), (f, ")! [ pob b ]

Si osservi come nell’alfabeto di stack

non è compreso il simbolo c che

denota la demarcazione tra le due

parti della stringa

Esempio stringhe palindrome 2

Automa per il riconoscimento del linguaggio L = {w w R}A = < {{s,f}, {a,b}, {a,b}, !, s, { f } > con ! che contiene le transizioni:

1. (( s, a, " ), (s, a)! [ push a]2. (( s b, " ), (s, b) [ push b]3. (( s, ", " ), (f, ")! !

4. (( f a, a ), (f, ")! [ pop a ]

5. (( f, b, b ), (f, ")! [ pob b ]

Stato Stringa di input stack transizione

s abbbba " "

s bbbba a 1

s bbba ba 2

s bba bba 2

f bba bba 3

f ba ba 5

f a a 5

f " " 4

Nell’applicazione della regola 3 la

macchina puo’ “scegliere” non

deterministicamente di andare nello stato

f senza consumare input o fare un

push del prossimo simbolo nello stack.

Si osservi come questa sia l’unica regola

variata rispetto all’automa precedente.

Esecuzione per abbbba