cerca
Informatica Teorica - Linguaggi liberi dal contesto
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Uni.IT-LinguaggiLiberiDalContesto History

Hide minor edits - Show changes to output

June 07, 2010, at 08:10 PM by ido -
Changed lines 34-35 from:
, dove ad esempio "r.1" indica l'applicazione della regola 1 della grammatica. Si noti che questa è solo una delle possibili stringhe ottenibili da G'_1_', un'altra sarebbe potuta essere 00B11, ottenuta con questa derivazione:
to:
, dove ad esempio "r.1" indica l'applicazione della regola 1 della grammatica. Si noti che questa è solo una delle possibili stringhe ottenibili da G'_1_', un'altra sarebbe potuta essere 00#11, ottenuta con questa derivazione:
Changed lines 37-39 from:
A --> 0A1 --> 00A11 --> 00B11
r.1 r.1 r.2@]
to:
A --> 0A1 --> 00A11 --> 00B11 --> 00#11
r.1 r.1 r.2 r.3@]
Added lines 74-75:
Tempi duri per i postini.
Changed line 87 from:
Siano ''u'', ''v'' e ''w'' stringhe di variabili e terminali, e [@A->w@] una regola della grammatica, possiamo dire che [@uAv@] genera [@uwu@], e lo scriviamo come [@uAv->uwv@]. Diciamo che ''u'' '''deriva''' ''v'', scritto ''u-'^*^'->v'' (una freccia con l'asterisco sopra), se ''u=v'' o se la sequenza u'_1_',u'_2_',..,u'_k_' esiste per k>=0 e \\
to:
Siano ''u'', ''v'' e ''w'' stringhe di variabili e terminali, e [@A->w@] una regola della grammatica, possiamo dire che [@uAv@] genera [@uwv@], e lo scriviamo come [@uAv->uwv@]. Diciamo che ''u'' '''deriva''' ''v'', scritto ''u-'^*^'->v'' (una freccia con l'asterisco sopra), se ''u=v'' o se la sequenza u'_1_',u'_2_',..,u'_k_' esiste per k>=0 e \\
Restore
June 06, 2010, at 06:44 PM by ido -
Changed lines 12-13 from:
Una ''grammatica'' consiste in un insieme di '''regole di sostituzione''', ognuna delle quali appare come una riga formata da un simbolo e una stringa separati da una freccia, ad esempio: [@A->CA50@]. I simboli a sinistra della freccia (generalmente lettere maiuscole) sono chiamati ''variabili'', mentre le stringhe possono essere composte da variabili o altri simboli chiamati ''terminali''. Tra tutte le variabili ce n'è una chiamata ''variabile iniziale'', che in genere compare nella parte sinistra della prima regola.
to:
Una ''grammatica'' consiste in un insieme di '''regole di sostituzione''', ognuna delle quali appare come una riga formata da un simbolo e una stringa separati da una freccia, ad esempio: [@A->CA50@]. I simboli a sinistra della freccia (generalmente lettere maiuscole) sono chiamati ''variabili'', mentre le stringhe a destra possono essere composte da variabili o altri simboli chiamati ''terminali''. Tra tutte le variabili ce n'è una chiamata ''variabile iniziale'', che in genere compare nella parte sinistra della prima regola.
Changed lines 85-86 from:
Siano ''u'', ''v'' e ''w'' stringhe di variabili e terminali, e [@A->w@] una regola della grammatica, possiamo dire che [@uAv@] genera [@uwu@], e lo scriviamo come [@uAv->uwv@]. Diciamo che ''u'' deriva ''v'', scritto ''u-'^*^'>v'' (una freccia con l'asterisco sopra), se ''u=v'' o se la sequenza u'_1_',u'_2_',..,u'_k_' esiste per k>=0 e ''u->u'_1_'->u'_2_'->..->u'_k_'->v''
to:
Siano ''u'', ''v'' e ''w'' stringhe di variabili e terminali, e [@A->w@] una regola della grammatica, possiamo dire che [@uAv@] genera [@uwu@], e lo scriviamo come [@uAv->uwv@]. Diciamo che ''u'' '''deriva''' ''v'', scritto ''u-'^*^'->v'' (una freccia con l'asterisco sopra), se ''u=v'' o se la sequenza u'_1_',u'_2_',..,u'_k_' esiste per k>=0 e \\
''u->u'_1_'->u'_2_'->..->u'_k_'->v''
Changed lines 98-100 from:
Una grammatica potrebbe generare una stessa stringa in modi diversi, seguendo diverse derivazioni; ne consegue che la stringa avrebbe più ''parse tree'', e quindi più significati. Questo non è un problema di per sé, ma lo diventa per certi tipi di applicazioni in cui l'interpretazione di una stringa deve essere univoca, come ad esempio nei linguaggi di programmazione. \\
Se una stessa stringa è generata da una grammatica in modi diversi, allora si dice che la striga è derivata in modo ''ambiguo''. Intuitivamente, una grammatica G si dice '''ambigua''' se genera una stringa in modo ambiguo.
to:
Una grammatica potrebbe generare la stessa stringa in modi diversi, seguendo diverse derivazioni; ne consegue che la stringa avrebbe più ''parse tree'', e quindi più significati. Questo non è un problema di per sé, ma lo diventa per certi tipi di applicazioni in cui l'interpretazione di una stringa deve essere univoca, come ad esempio nei linguaggi di programmazione. \\
Se una stessa stringa è generata da una grammatica in modi diversi, allora si dice che la stringa è derivata in modo ''ambiguo''. Intuitivamente, una grammatica G si dice '''ambigua''' se genera una stringa in modo ambiguo.
Changed line 119 from:
''S -> S'_1_' | S'_2_' | ... | S'_k_''\\
to:
''S -> S'_1_' | S'_2_' | ... | S'_k_'''\\
Changed line 142 from:
, dove ''a'' è un qualsiasi terminale, A B e C sono una qualsiasi variabile, dove però solo A è variabile iniziale. E' inoltre consentita la regola ''S -> ε'', dove S è la variabile iniziale.
to:
, dove ''a'' è un qualsiasi terminale, A B e C sono una qualsiasi variabile, ma solo A è variabile iniziale. E' inoltre consentita la regola ''S -> ε'', dove S è la variabile iniziale.
Changed lines 161-163 from:
# per ogni occorrenza di A nella parte destra di una regola, aggiungiamo una nuova regola in cui A non vi compare. In pratica, se abbiamo una regola del tipo [@R->uAv@] (dove ''u'' e ''v'' sono stringhe di variabili e/o terminali), la facciamo diventare: '''R->uAv|uv''';
# eliminiamo tutte le regole nella forma ''A->ε''.
to:
# eliminiamo tutte le regole nella forma ''A->ε'';
# per ogni occorrenza di A nella parte destra di una regola, aggiungiamo una nuova regola in cui A non vi compare. In pratica, se abbiamo una regola del tipo [@R->uAv@] (dove ''u'' e ''v'' sono stringhe di variabili e/o terminali), la facciamo diventare: '''R->uAv|uv'''.
Changed lines 166-167 from:
# ogni volta che appare la regola [@B->u@], aggiungiamo la regola '''A->u''';
# eliminiamo tutte le regole unitarie nella forma ''A->B''.
to:
# eliminiamo tutte le regole unitarie nella forma ''A->B'';
# ogni volta che appare la regola [@B->u@], aggiungiamo la regola '''A->u'''.
Restore
June 05, 2010, at 12:12 PM by ido -
Changed line 187 from:
Applichiamo il ''Passo (1)''
to:
Applichiamo il '''Passo (1)'''
Changed lines 194-195 from:
Applichiamo il ''Passo (2)''
->''eliminiamo la regola B->ε
to:
Applichiamo il '''Passo (2)'''
->''eliminiamo la regola B->ε''
Changed line 201 from:
->''eliminiamo la regola A->ε
to:
->''eliminiamo la regola A->ε''
Changed line 207 from:
Applichiamo il ''Passo (3)''
to:
Applichiamo il '''Passo (3)'''
Changed line 232 from:
Applichiamo il ''Passo (4)''
to:
Applichiamo il '''Passo (4)'''
Restore
June 05, 2010, at 12:11 PM by ido -
Changed lines 28-29 from:
Ad esempio, che stringhe genera la nostra grammatica G'_1_'? Dovremo ripetere i passi appena descritti facendo le opportune sostituzioni, secondo una sequenza che prende il nome di '''derivazione'''. Facciamo allora una derivazione di G'_1_':\\
to:
Ad esempio, che stringhe genera la nostra grammatica G'_1_'? Dovremo ripetere i passi appena descritti facendo le opportune sostituzioni, secondo una sequenza che prende il nome di '''derivazione'''. Facciamo allora una derivazione di G'_1_':
Changed lines 33-35 from:
, dove ad esempio "r.1" indica l'applicazione della regola 1 della grammatica. Si noti che questa è solo una delle possibili stringhe ottenibili da G'_1_', un'altra sarebbe potuta essere 00B11, ottenuta con questa derivazione:\\
to:
, dove ad esempio "r.1" indica l'applicazione della regola 1 della grammatica. Si noti che questa è solo una delle possibili stringhe ottenibili da G'_1_', un'altra sarebbe potuta essere 00B11, ottenuta con questa derivazione:
Changed lines 85-87 from:
Siano ''u'', ''v'' e ''w'' stringhe di variabili e terminali, e [@A->w@] una regola della grammatica, possiamo dire che [@uAv@] genera [@uwu@], e lo scriviamo come [@uAv->uwv@]. Diciamo che ''u'' deriva ''v'', scritto ''u-'^*^'>v'' (una freccia con l'asterisco sopra), se ''u=v'' o se la sequenza u'_1_',u'_2_',..,u'_k_' esiste per k>=0 e\\
''u->u'_1_'->u'_2_'->..->u'_k_'->v''
to:
Siano ''u'', ''v'' e ''w'' stringhe di variabili e terminali, e [@A->w@] una regola della grammatica, possiamo dire che [@uAv@] genera [@uwu@], e lo scriviamo come [@uAv->uwv@]. Diciamo che ''u'' deriva ''v'', scritto ''u-'^*^'>v'' (una freccia con l'asterisco sopra), se ''u=v'' o se la sequenza u'_1_',u'_2_',..,u'_k_' esiste per k>=0 e ''u->u'_1_'->u'_2_'->..->u'_k_'->v''
Changed line 97 from:
Una grammatica potrebbe generare una stessa stringa in modi diversi, seguendo diverse derivazioni; ne consegue che la stringa avrebbe più ''parse''tree'', e quindi più significati. Questo non è un problema di per sé, ma lo diventa per certi tipi di applicazioni in cui l'interpretazione di una stringa deve essere univoca, come ad esempio nei linguaggi di programmazione. \\
to:
Una grammatica potrebbe generare una stessa stringa in modi diversi, seguendo diverse derivazioni; ne consegue che la stringa avrebbe più ''parse tree'', e quindi più significati. Questo non è un problema di per sé, ma lo diventa per certi tipi di applicazioni in cui l'interpretazione di una stringa deve essere univoca, come ad esempio nei linguaggi di programmazione. \\
Changed line 141 from:
, dove ''a'' è un qualsiasi terminale, A B e C sono una qualsiasi variabile, dove però solo A è variabile iniziale. E' inoltre consentita la regola [@S -> ε@], dove S è la variabile iniziale.
to:
, dove ''a'' è un qualsiasi terminale, A B e C sono una qualsiasi variabile, dove però solo A è variabile iniziale. E' inoltre consentita la regola ''S -> ε'', dove S è la variabile iniziale.
Changed line 160 from:
# per ogni occorrenza di A nella parte destra di una regola, aggiungiamo una nuova regola in cui A non vi compare. In pratica, se abbiamo una regola del tipo [@R->uAv@] (dove ''u'' e ''v'' sono stringhe di variabili e/o terminali), la facciamo diventare: [@R->uAv|uv@];
to:
# per ogni occorrenza di A nella parte destra di una regola, aggiungiamo una nuova regola in cui A non vi compare. In pratica, se abbiamo una regola del tipo [@R->uAv@] (dove ''u'' e ''v'' sono stringhe di variabili e/o terminali), la facciamo diventare: '''R->uAv|uv''';
Changed line 165 from:
# ogni volta che appare la regola [@B->u@], aggiungiamo la regola [@A->u@];
to:
# ogni volta che appare la regola [@B->u@], aggiungiamo la regola '''A->u''';
Changed line 187 from:
Applichiamo il ''Passo (1)''\\
to:
Applichiamo il ''Passo (1)''
Changed line 194 from:
Applichiamo il ''Passo (2)''\\
to:
Applichiamo il ''Passo (2)''
Changed line 207 from:
Applichiamo il ''Passo (3)''\\
to:
Applichiamo il ''Passo (3)''
Changed line 232 from:
Applichiamo il ''Passo (4)''\\
to:
Applichiamo il ''Passo (4)''
Restore
June 05, 2010, at 12:08 PM by ido -
Added lines 1-241:
(:title Informatica Teorica - Linguaggi liberi dal contesto :)
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
----

%titolo%''':: Informatica Teorica - Linguaggi liberi dal contesto ::'''

%center% %sottotitolo% Appunti & Dimostrazioni del 17 Marzo

!!Concetti iniziali
Gli automi a stati finiti ci permettono di descrivere linguaggi, ma solo quelli regolari. E tutti gli altri? C'è bisogno di strumenti più potenti, come le '''grammatiche libere dal contesto''', che permettono di generare - manco a dirlo - ''linguaggi liberi dal contesto''.

Una ''grammatica'' consiste in un insieme di '''regole di sostituzione''', ognuna delle quali appare come una riga formata da un simbolo e una stringa separati da una freccia, ad esempio: [@A->CA50@]. I simboli a sinistra della freccia (generalmente lettere maiuscole) sono chiamati ''variabili'', mentre le stringhe possono essere composte da variabili o altri simboli chiamati ''terminali''. Tra tutte le variabili ce n'è una chiamata ''variabile iniziale'', che in genere compare nella parte sinistra della prima regola.

Facciamo un esempio definendo una grammatica G'_1_':
->A->0A1
->A->B
->B->#

In G'_1_' abbiamo due variabili (A e B, di cui A è quella iniziale) e tre simboli terminali (0, 1 e #).

!!!Come si usa una grammatica
Il sistema con cui le grammatiche permettono di descrivere un linguaggio, passa attraverso la generazione di ogni sua stringa. Per farlo bisogna seguire alcuni passaggi:
# scrivere la variabile iniziale;
# per ogni variabile, trovare una regola in cui essa compaia nella parte sinistra (rispetto alla freccia);
# sostituire la variabile con la parte destra della regola;
# ripetere (2) e (3) finché non rimangono variabili.

Ad esempio, che stringhe genera la nostra grammatica G'_1_'? Dovremo ripetere i passi appena descritti facendo le opportune sostituzioni, secondo una sequenza che prende il nome di '''derivazione'''. Facciamo allora una derivazione di G'_1_':\\
[@
A --> 0A1 --> 00A11 --> 000A111 --> 000B111 --> 000#111
r.1 r.1 r.1 r.2 r.3@]
, dove ad esempio "r.1" indica l'applicazione della regola 1 della grammatica. Si noti che questa è solo una delle possibili stringhe ottenibili da G'_1_', un'altra sarebbe potuta essere 00B11, ottenuta con questa derivazione:\\
[@
A --> 0A1 --> 00A11 --> 00B11
r.1 r.1 r.2@]

I possibili percorsi di derivazione possono essere mostrati graficamente con i ''parse tree''. Ad esempio il ''parse tree'' per la stringa 000#111 nella grammatica G'_1_' è:

%center%Attach:IT-parseTree.gif

Per far capire che con le grammatiche libere dal contesto si possono descrivere linguaggi ben più complicati, facciamo un esempio di grammatica G'_2_' che descriva una porzione della lingua italiana:
[@
<frase> -> <soggetto-frase> <predicato-frase>
<soggetto-frase> -> <nome-comp> | <nome-comp> <preposiz-frase>
<predicato-frase> -> <predicato-comp> | <predicato-comp> <preposiz-frase>
<preposiz-frase> -> <preposiz> <nome-comp>
<nome-comp> -> <articolo> <nome>
<predicato-comp> -> <predicato> | <predicato> <soggetto-frase>
<articolo> -> un | il
<nome> -> cinghiale | postino | tornado
<predicato> -> amoreggia | rincorre | parla
<preposiz> -> con@]

Con cui ad esempio si può formare l'illuminante frase "il tornado rincorre un postino", o la seguente "un cinghiale amoreggia con il postino":

[@
<frase> -> <soggetto-frase> <predicato-frase>
-> <nome-comp> <predicato-frase>
-> <articolo> <nome> <predicato-frase>
-> <articolo> <nome> <predicato-comp> <preposiz-frase>
-> <articolo> <nome> <predicato> <preposiz-frase>
-> <articolo> <nome> <predicato> <preposiz> <nome-comp>
-> <articolo> <nome> <predicato> <preposiz> <articolo> <nome>
-> un <nome> <predicato> <preposiz> <articolo> <nome>
-> un cinghiale <predicato> <preposiz> <articolo> <nome>
-> un cinghiale amoreggia <preposiz> <articolo> <nome>
-> un cinghiale amoreggia con <articolo> <nome>
-> un cinghiale amoreggia con il <nome>
-> un cinghiale amoreggia con il postino@]

!!Definizione formale
Diamo finalmente la definizione di grammatica libera dal contesto, o '''CFG''' (context-free grammar).

>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Una '''grammatica libera dal contesto''' è una 4-upla (V,&#931;,R,S), dove:
#V è l'insieme finito delle '''variabili''';
#&#931; è l'insieme finito, disgiunto da V, dei '''terminali''';
#R è l'insieme finito delle '''regole''', ognuna formata da una variabile e da una stringa di variabili e terminali;
#S &#8712; V è la variabile iniziale.
>><<

Siano ''u'', ''v'' e ''w'' stringhe di variabili e terminali, e [@A->w@] una regola della grammatica, possiamo dire che [@uAv@] genera [@uwu@], e lo scriviamo come [@uAv->uwv@]. Diciamo che ''u'' deriva ''v'', scritto ''u-'^*^'>v'' (una freccia con l'asterisco sopra), se ''u=v'' o se la sequenza u'_1_',u'_2_',..,u'_k_' esiste per k>=0 e\\
''u->u'_1_'->u'_2_'->..->u'_k_'->v''

A questo punto possiamo definire il '''linguaggio della grammatica''' come:\\
''{w &#8712; &#931;* | S-'^*^'>w}''

Riportandola sul pratico, nella nostra vecchia cara grammatica G'_1_' avremo che:
* V = {A,B}
* &#931; = {0,1,#}
* S = A
* R = "A->0A1", "A->B", "B->#"

!!!Ambiguità
Una grammatica potrebbe generare una stessa stringa in modi diversi, seguendo diverse derivazioni; ne consegue che la stringa avrebbe più ''parse''tree'', e quindi più significati. Questo non è un problema di per sé, ma lo diventa per certi tipi di applicazioni in cui l'interpretazione di una stringa deve essere univoca, come ad esempio nei linguaggi di programmazione. \\
Se una stessa stringa è generata da una grammatica in modi diversi, allora si dice che la striga è derivata in modo ''ambiguo''. Intuitivamente, una grammatica G si dice '''ambigua''' se genera una stringa in modo ambiguo.

!!!Esercizietto 1
Data la grammatica G'_3_' = ({S},{a,b},R,S} e l'insieme di regole S->aSb|SS|&#949; , generare alcune stringhe appartenenti a L(G'_3_').

'''Soluzione'''

[@
S --> aSb --> aaSbb --> aaSSbb --> aaaSbaSbbb --> aaababbb
r.1 r.1 r.2 r.1 r.3@]

oppure possono uscire cose come: [@abab@], [@aaabbb@], [@aabaabbb@].

!!!Esercizietto 2
Determinare la grammatica per il linguaggio:\\
{0'^n^'1'^n^' | n>=0}U{1'^n^'0'^n^' | n>=0}

'''Soluzione'''

Dovrò definire separatamente una grammatica per la prima e la seconda parte, poi ne faccio un unione aggiungendo una nuova regola iniziale (qualcosa di molto simile a quanto visto nel capitolo del [[nondeterminismo->IT-Nondeterminismo]]). In pratica se abbiamo ''k'' grammatiche da unire, la nuova grammatica avrà come prima regola:\\
''S -> S'_1_' | S'_2_' | ... | S'_k_''\\
, dove le variabili S'_i_' sono le variabili iniziali di ogni grammatica.

Torniamo al nostro esercizio e costruiamo la grammatica S'_1_' per la prima parte del linguaggio, e la S'_2_' per la seconda.

Linguaggio L'_1_': {0'^n^'1'^n^' | n>=0}\\
Grammatica G'_1_': '''S'_1_' -> 0S'_1_'1 | &#949;'''

Linguaggio L'_2_': {1'^n^'0'^n^' | n>=0}\\
Grammatica G'_2_': '''S'_2_' -> 1S'_1_'0 | &#949;'''

Per quanto detto finora, facendo l'unione di G'_1_' e G'_2_' otteniamo:
->'''S -> S'_1_' | S'_2_''''
->'''S'_1_' -> 0S'_1_'1 | &#949;'''
->'''S'_2_' -> 1S'_1_'0 | &#949;'''

!!Forma normale di Chomsky
La ''forma normale di Chomsky'' ci permette di riscrivere una grammatica libera dal contesto in forma più compatta e semplificata. Ci tornerà molto utile in futuro, soprattutto se non sappiamo che nome dare al secondo criceto ("Chomsky & Pumping-lemma", that's all folks!).

>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Una CFG è nella '''forma normale di Chomsky''' se ogni regola è nella forma:
->[@A -> BC@]
->[@A -> a@]
, dove ''a'' è un qualsiasi terminale, A B e C sono una qualsiasi variabile, dove però solo A è variabile iniziale. E' inoltre consentita la regola [@S -> &#949;@], dove S è la variabile iniziale.
>><<

!!!Teorema 1 - sulla forma normale di Chomsky
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Ogni linguaggio libero dal contesto è generato da una grammatica libera dal contesto nella forma normale di Chomsky.
>><<

'''Dimostrazione'''

Dato che per definizione un linguaggio libero dal contesto è generato da una CFG, non dobbiamo fare altro che dimostrare che ogni grammatica libera dal contesto G può essere espressa nella forma normale di Chomsky. Lo facciamo per costruzione, scandendo i vari passi.

''Passo (1)''\\
Definiamo una nuova variabile iniziale S'_0_' e aggiungiamo la regola:
->'''S'_0_'->S'''
, dove S era la variabile iniziale di G.

''Passo (2)''\\
Dobbiamo far sparire tutte le regole espresse nella forma ''A->&#949;'', dove A è una variabile diversa da quella iniziale. Si fa in due tempi:
# per ogni occorrenza di A nella parte destra di una regola, aggiungiamo una nuova regola in cui A non vi compare. In pratica, se abbiamo una regola del tipo [@R->uAv@] (dove ''u'' e ''v'' sono stringhe di variabili e/o terminali), la facciamo diventare: [@R->uAv|uv@];
# eliminiamo tutte le regole nella forma ''A->&#949;''.

''Passo (3)''\\
Dobbiamo far sparire tutte le regole unitarie espresse nella forma ''A->B''. Anche in questo caso si opera in due tempi:
# ogni volta che appare la regola [@B->u@], aggiungiamo la regola [@A->u@];
# eliminiamo tutte le regole unitarie nella forma ''A->B''.

''Passo (4)''\\
Concludiamo la costruzione convertendo tutte le altre regole nella forma appropriata. In particolare dovremo individuare ogni regola del tipo:
->''A -> u'_1_'u'_2_'..u'_k_''', con k>=3 e ogni u'_i_' variabile o terminale
, e sostituirla con le regole:
->'''A -> u'_1_'A'_1_''''
->'''A'_1_' -> u'_2_'A'_2_''''
->'''A'_2_' -> u'_3_'A'_3_''''
->...
->'''A'_k-2_' -> u'_k-1_'u'_k_'''', dove le varie A'_i_' sono nuove variabili.
Quando arriviamo ad avere tutte regole con k=2, sostituiamo il terminale u'_i_' nelle regole precedenti con la nuova variabile ''U'_i_''', e aggiungiamo la regola: '''U'_i_'->u'_i_''''.

!!!Esempio di conversione
Tra il dire e il fare c'è di mezzo il mare. Imbarchiamoci per convertire una CFG nella corrispettiva forma normale di Chomsky.

La grammatica G da convertire è la seguente:
->S -> ASA | aB
->A -> B | S
->B -> b | &#949;

Applichiamo il ''Passo (1)''\\
->''aggiungiamo una nuova variabile iniziale''
-->'''S'_0_' -> S'''
-->S -> ASA | aB
-->A -> B | S
-->B -> b | &#949;

Applichiamo il ''Passo (2)''\\
->''eliminiamo la regola B->&#949;
-->S'_0_' -> S
-->S -> ASA | aB | '''a'''
-->A -> B | S | '''&#949;'''
-->B -> b {-| &#949;-}

->''eliminiamo la regola A->&#949;
-->S'_0_' -> S
-->S -> ASA | aB | a '''| SA | AS | S'''
-->A -> B | S {-| &#949;-}
-->B -> b

Applichiamo il ''Passo (3)''\\
->''eliminiamo la regola unitaria S->S''
->S'_0_' -> S '''| ASA | aB | a | SA | AS'''
->S -> ASA | aB | a | SA | AS {-| S-}
->A -> B | S
->B -> b

->''eliminiamo la regola unitaria S'_0_'->S''
->S'_0_' -> {-S |-} ASA | aB | a | SA | AS
->S -> ASA | aB | a | SA | AS
->A -> B | S
->B -> b

->''eliminiamo la regola unitaria A->B''
->S'_0_' -> ASA | aB | a | SA | AS
->S -> ASA | aB | a | SA | AS
->A -> {-B |-} S '''| b'''
->B -> b

->''eliminiamo infine la regola unitaria A->S''
->S'_0_' -> ASA | aB | a | SA | AS
->S -> ASA | aB | a | SA | AS
->A -> {-S |-} b '''| ASA | aB | a | SA | AS'''
->B -> b

Applichiamo il ''Passo (4)''\\
->''convertiamo le regole rimanenti nella forma appropriata''
->S'_0_' -> AA'_1_' | UB | a | SA | AS
->S -> AA'_1_' | UB | a | SA | AS
->A -> b | AA'_1_' | UB | a | SA | AS
->A'_1_' -> SA
->U -> a
->B -> b


----
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
Restore