Forma normal de Chomsky

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é

• Jerarquia de Chomsky

Bibliografia

• Sipser, Michael. Introduction to the Theory of Computation. ISBN 978-0-619-21764-8.