Automa finito deterministico (DFA), Automa finito deterministico (DFA)
Linguaggi context-free
…o CFL, è un metodo più potente per descrivere linguaggi.
Es. 1: grammatica context-free che genera a^n U b^n
Cos’è una grammatica?
Una grammatica consiste di un insieme di regole di sostituzione, anche chiamate produzioni. Ogni regola appare come una linea nella grammatica, costituita da un simbolo e una stringa separati da una freccia. Il simbolo è chiamato variabile, La stringa consiste di variabili e altri simboli chiamati terminali.
Ci sono dei linguaggi che possono essere espressi semplicemente dal punto di vista linguistico ma non possono essere riconosciuti dagli automi finiti deterministici o dagli automi finiti non deterministici.
Es. 2: grammatica context-free che descrive un frammento della lingua inglese, permette di generare parole grammaticalmente corrette
Definizione formale di grammatica context-free
*Hint: I compilatori funzionano con grammatica context-free (Python ti aiuta nella sintassi ma non nell’espressione dell’algoritmo). Un compilatore traduce il codice scritto in un linguaggio di programmazione in un’altra forma. Per farlo il compilatore estrae il significato del codice da compilare in un processo chiamato parsing.
Dal DFA è facile costruire una grammatica context-free che genera un linguaggio regolare.
Concetto di ambiguità
La grammatica può generare la stessa stringa in più modi diversi. Ciò significa che la stessa stringa può essere generata da più alberi (processi ad albero) diversi.
Una grammatica non ambigua corrisponde ad un albero sintattico unico. Attenzione! Un linguaggio è context free se e solo se…