Forma normal de Chomsky

De Viquipèdia
Dreceres ràpides: navegació, cerca

En la informàtica, una gramàtica lliure de context és aquella que està en la forma normal de Chomsky si totes les seves regles són de la forma:

A \rightarrow BC
A \rightarrow \alpha

on \alpha és qualsevol símbol terminal i A, B i C són variables, B i C no poden ser la variable inicial. També es permet la regla:

S \rightarrow \varepsilon

on S és la variable inicial i \varepsilon la paraula buida (també pot estar representada per λ).

Vegeu també[modifica | modifica el codi]

Bibliografia[modifica | modifica el codi]