El tercer tipo de gramática formal

Las gramáticas de tipo 3 también se denominan gramáticas regulares y corresponden a autómatas de estados finitos. La gramática normal tiene muchas definiciones equivalentes. Podemos definir de manera equivalente la gramática regular en términos de gramática lineal izquierda o gramática lineal derecha. La gramática lineal izquierda requiere que el lado izquierdo de una producción solo pueda contener un símbolo no terminal, y el lado derecho de una producción solo pueda ser una cadena vacía, un símbolo terminal o un símbolo no terminal seguido por un símbolo terminal. La gramática lineal derecha requiere que el lado izquierdo de una producción sólo pueda contener un símbolo no terminal, y que el lado derecho de una producción sólo pueda ser una cadena vacía, un símbolo terminal o un símbolo terminal seguido de un símbolo no terminal. Sobre la base de la gramática de tipo 2, satisface: A→α|αB (lineal derecha) o A→α|Bα (lineal izquierda).

Si es: A->A, A->aB, B->a, B->CB, cumple con los requisitos de gramática tipo 3. Pero si la derivación es: a->ab, A->aB, B->a, B->CB o la derivación es: A->A, A->Ba,B ->a,B -> CB no cumple los requisitos para un método de tipo 3. Específicamente, a->a en el ejemplo a->ab, A->aB, B->a, B->cB no cumple con la definición de gramática tipo 3, y lo siguiente a->ab Simplemente cámbielo a la forma de "un símbolo no terminal + un símbolo terminal" (es decir, aB). Ejemplo a->A, A->Ba,B->a,B->Si B->CB se cambia a B->La forma de Bc es correcta porque A→ Los dos conjuntos de reglas α |αB (lineal derecha) y A→α|Bα (lineal izquierda) no pueden aparecer en una gramática al mismo tiempo. Solo uno de ellos puede satisfacerse por completo, lo que puede considerarse como una gramática de tipo 3.

Nota: En el ejemplo anterior, las letras mayúsculas representan caracteres no terminales y las letras minúsculas representan terminadores.