Jerarquia chomsky

En 1959 Noam Chomsky clasifico las gramáticas en cuatro familias. Las gramáticas no restringidas, sensibles al contexto, independientes del contexto y las gramáticas regulares que se conocen comogramáticas de tipo cero, uno, dos y tres respectivamente. Los lenguajes que resultan de dichas gramáticas también se identifican con lenguajes de tipo cero, uno, dos y tres. A esta jerarquía de lenguajese le conoce como la jerarquía de chomsky.

Gramática Regular: Es aquella gramática cuyas reglas de reescritura tienen las siguientes restricciones:

1.- El lado izquierdo de cualquier regla dereescritura debe consistir en un solo no terminal, el lado derecho debe ser un terminal seguido por un no terminal, o un solo terminal o la cadena vacía
Ejemplo:
Z yX
X y
X
Las siguientesreglas de reescritura no estarían permitidas en una gramática regular.
Ejemplo:
yW X
X xZy
YX WvZ

En una gramática regular cualquier regla de la forma N x podría remplazarse con el par de reglassiguientes:
N xX
X

Donde X es un no terminal que no aparece en ningún otro lugar de la gramática, sin alterar el conjunto de cadenas que podría generar la gramática.
N xX x = x
Laimportancia de las gramáticas regulares reside en que los lenguajes generados por ellas son exactamente aquellos que reconocen los autómatas finitos.
NOTA:
se interpreta como «puede ser», «se componede», «es sustituida por».
se interpreta como «o» ejemplo: E A y E B se unen en E AB.
se interpreta como «derivar», «produce» o «genera».
Gramáticas independientes del contexto.
A diferencia delas gramáticas regulares, estas gramáticas no tienen restricciones con respecto a la forma del lado derecho de sus reglas de reescritura aunque aun se requiere que el lado izquierdo de cada regla seaun no terminal. La siguiente es una gramática independiente del contexto, pero no es regular.
S zMNz
M aMa
M z
N bNb
N z

El termino independiente del contexto refleja que, como el lado…