Differenze tra le versioni di "Grammatica libera dal contesto"

*gli elementi di <math>P</math> sono nella forma
::<math>N \longrightarrow (\Sigma \cup N)^*</math>
 
== Esempi ==
 
=== Esempio 1 ===
 
Una semplice grammatica context-free:
:S &rarr; aSb | &epsilon;
dove il metasimbolo '''|''' è una [[disgiunzione logica]], usata per separare multiple opzioni.
Questa grammatica genera il linguaggio <math> \{ a^n b^n : n \ge 0 \} </math>, il quale è un [[linguaggio lineare|linguaggio non regolare]].
 
----
 
=== Esempio 2 ===
Ecco una grammatica context-free per espressioni algebriche con infissi sintatticamente
 
----
 
=== Esempio 3 ===
Una grammatica context-free per il linguaggio consistente in tutte le stringhe nell'insieme {a,b} che contengono un numero diverso di a e di b è
:S &rarr; U | V
:U &rarr; TaU | TaT
:V &rarr; TbV | TbT
:T &rarr; aTbT | bTaT | &epsilon;
T può generare tutte le strighe con lo stesso numero di a e b, U genera tutte le stringhe con più a che b e V genera tutte le stringhe con meno a di b.
----
 
=== Esempio 4 ===
Un altro esempio di linguaggio context-free è <math> \{ a^n b^m c^{m+n} : n \ge 0, m \ge 0 \} </math>. Non è un linguaggio regolare, ma è context free dal momento che può essere generato dalla seguente CFG (Context Free Grammar):
:S &rarr; aSc | B
:B &rarr; bBc | &epsilon;
----
 
=== Altri esempi ===
Le grammatiche context-free non sono limitate alle applicazioni matematiche (linguaggi "formali").
La grammatica del [[Lojban]], un linguaggio artificiale con un immenso potere espressivo, è context-free, e non ambiguo. Recentemente si è pensato che il genere poetico Venpa del [[lingua Tamil|Tamil]] sia guidato da una grammatica context-free.
 
==Voci correlate==
Utente anonimo