Forma normale di Chomsky

Una grammatica formale è in forma normale di Chomsky se tutte le sue regole di produzione sono di una delle seguenti forme:

$UN$${\ displaystyle \ rightarrow \,}$${\ displaystyle aC}$o

$UN$${\ displaystyle \ rightarrow \,}$α

dove , e sono simboli (o variabili) non terminali e α è un simbolo terminale. $UN$$B.$$C$

Ogni linguaggio privo di contesto che non ha la stringa vuota è esprimibile per mezzo di una grammatica in forma normale di Chomsky (GFNCH) e viceversa. Inoltre, data una grammatica context-free , è possibile algoritmicamente produrre un GFNCH equivalente, cioè uno che generi lo stesso linguaggio.

Definizione alternativa

In alcuni testi puoi trovare una definizione di GFNCH tale che qualsiasi GFNCH produca qualsiasi linguaggio privo di contesto e allo stesso modo che per qualsiasi linguaggio privo di contesto ci sia un GFNCH che lo definisce. Questa definizione difficilmente differisce nel consentire una regola ε della seguente forma:

$UN$${\ displaystyle \ rightarrow \,}$${\ displaystyle aC}$o

$UN$${\ displaystyle \ rightarrow \,}$α o

$sì$${\ displaystyle \ rightarrow \,}$ε

dove è il simbolo distinto (o iniziale) della grammatica, è un simbolo non terminale (o variabile) e sono anche simboli non terminali ma distinti , α è un simbolo terminale e ε è la stringa nulla (o vuota). $sì$$UN$$B.$$C$$sì$

Vedi anche

• Grammatica (automa)
• Greibach forma normale