(:title Traduttori - Lezione del 5 marzo 2009:)
:: Traduttori - Lezione del 5 marzo 2009 ::
Torna alla pagina di Traduttori
Definizione formale di derivazione
Una derivazione si scrive così, in termini formali: ν -> γ, dove la prima lettera ν è la ni dell'alfabeto greco.
Quindi, da ν si deriva γ per la grammatica G sse:
- ν = σAτ
- γ = σατ
- A -> α appartenente a P
Spieghiamo bene queste cose:
- Le prime due regole mi dicono come sono fatte le stringhe ν e γ
- σ e τ possono essere simboli terminali o no, e possono anche essere eventualmente vuote
- A è un simbolo non terminale
- α può essere un simbolo terminale o no
In pratica, queste regole mi stanno dicendo che posso andare da ν a γ se esiste una regola che trasforma una qualche parte di ν in modo tale che la renda uguale a γ. Dal punto di vista teorico, niente di nuovo, però è così che si scrive formalmente.
Una derivazione si dice diretta se basta una sola produzione per andare da ν a γ.
Una derivazione è invece indiretta se c'è bisogno di una serie di stringhe intermedie, e delle condizioni così fatte:
- ν = w0
- γ = wn
- per ogni i da 0 a n, wi -> wi+1
Questo vuol dire che da ν si deriva γ se esiste una sequenza di stringhe frutto di successive derivazioni consecutive, che partono proprio da ν e arrivano a γ.
La derivazione indiretta si scrive ν ->* γ (l'asterisco dovrebbe essere sopra il ->).
Derivazioni canoniche
Supponiamo di avere una stringa che voglio derivare:
aAbcBaA
Le lettere maiuscole A e B sono simboli non terminali, che quindi andranno sostituiti. In generale si sottolinea il simbolo non terminale che vado a derivare. In questo caso, se scelgo di derivare la prima A, scriverei
a(+A+)bcBaA -> adbcBaA
(notate che mi sono anche inventato la produzione A -> db)
La derivazione canonica sinistra è una derivazione in cui scelgo di sviluppare sempre il non terminale più a sinistra nella mia stringa.
Nella derivazione canonica sinistra invece sviluppo sempre per primo il non terminale più a destra.
Fra un po' vedremo a che cosa serve questa distinzione apparentemente inutile.
Definizione formale di linguaggio
Data una grammatica G = (NT, T, S, P), il linguaggio generato da G lo si può segnare così: Lg, oppure così: L(G).
La sua definizione formale è questa:
L(G) = {w appartenente a T* | S ->* w}
che vuol dire: è composto da tutte e sole le stringhe w appartenenti all'alfabeto terminale della grammatica (ovvero tutte le stringhe producibili con i simboli terminali T della grammatica G), tali che esista una derivazione, anche indiretta, che parta dall'assioma della grammatica, cioè S, e porti alla stringa w.
Intuitivamente questo concetto era già chiaro, e questa è solo la sua formalizzazione.
Classificazione delle grammatiche
Chomsky ha classificato, tempo addietro, le grammatiche, a seconda dei vincoli che vengono posti sulle regole di produzione.
Questa distinzione è importante perché permette di riassumere certe proprietà delle grammatiche e dei linguaggi da esse generate, e ci permette di stabilire che tipo di macchina sarà poi in grado di riconoscere e/o generare quella particolare grammatica.
Grammatica di tipo 0
La grammatica di tipo 0 non ha nessun vincolo sulle produzioni. Viene anche detta grammatica a struttura di frase. I linguaggi generati da questa grammatica sono anche detti ricorsivamente enumerabili.
Grammatica di tipo 1
E' detta grammatica dipendente dal contesto.
Le regole di questa grammatica hanno la seguente forma:
γAδ -> γαδ
con i seguenti vincoli:
- A appartiene all'insieme dei NT
- γ e δ appartengono a (NT U T)*
- α appartiene a (NT U T)+
L'appartenenza di γ e δ a (NT U T)* vuol dire che possono essere una qualsiasi combinazione, eventualmente composta dalla stringa nulla, di tutti i simboli terminali o non terminali.
Invece, dire che α appartiene a (NT U T)+ vuol dire che la stringa nulla è esclusa: α deve essere qualcosa.
Torna alla pagina di Traduttori