Gramáticas
Al introducir criterios más o menos restrictivos sobre la forma de las reglas gramaticales, obtenemos clases gramaticales jerárquicas (tipos de gramáticas), ordenadas por inclusión. La clasificación de gramáticas, definida en 1957 por Noam Chomsky, distingue cuatro clases.
Clasificación de Chomsky
Tipo 0: sin restricción en las reglas.
Tipo 1: Gramáticas contextuales o sensibles al contexto. Las reglas de R son de la forma:
- uAv → uwv con A ∈ N, u, v ∈ (N ∪ T)∗ y w ∈ (N ∪ T)+
- En otras palabras, el símbolo no terminal A se reemplaza por w si tenemos los contextos u a la izquierda y v a la derecha.
Tipo 2: gramáticas libres de contexto. Las reglas de R son de la forma:
- A → w con A ∈ N y w ∈ (N ∪ T)∗
- En otras palabras, el lado izquierdo de cada regla consta de un solo símbolo no terminal.
Tipo 3: gramáticas regulares
- a la derecha. Las reglas de R son de la forma
A → aB o A → a con A, B ∈ N y a ∈ T - a la izquierda. Las reglas de R son de la forma
A → Ba o A → a con A, B ∈ N y a ∈ T - En otras palabras, el lado izquierdo de cada regla consta de un solo símbolo no terminal, y el lado derecho consta de un símbolo terminal y posiblemente un símbolo no terminal. Para las gramáticas regulares a la derecha, el símbolo no terminal siempre debe estar a la derecha del símbolo terminal mientras que para las gramáticas regulares a la izquierda debe estar a la izquierda.
Ejemplo 1
Consideramos el lenguaje L de palabras en {0, 1} que representan incluso enteros en base 2 sin signo (todas las palabras de este lenguaje terminan con 0 y no comienzan con 0, excepto el entero cero). Defina formalmente L y construya una gramática regular que describa L.
El idioma tiene la siguiente forma: L = {0, 1u0 / u ∈ {0, 1}∗}
Definimos la gramática regular de la mano derecha G = (T, N, S, R) donde
T = {0, 1}
N = {S, U}
R = {S → 0 | 1U
U → 1U | 0U | 0}
así como la gramática izquierda regular G = (T, N, S, R) donde
T = {0, 1}
N = {S, U}
R = {S → 0 | U0
U → U1 | U0 | 1}
Preferiblemente, siempre tomamos la gramática normal de la mano derecha para el estudio de estados futuros en autómatas.
Ejemplo 2
Aquí están las producciones gramaticales: P → aP, P → aQ, Q → bP, Q → R, R → bR, R → cQ, R → bP, R → ε. Los no terminales de la gramática son {P, Q, R}, el símbolo inicial es P.
Denotando con Xpag, Xq, Xr los lenguajes aceptados de los estados P, Q y R respectivamente, el sistema de ecuaciones para estos lenguajes es:
ES 
FR 
EN