Chomsky clasificó las gramáticas en cuatro grandes grupos : G0, G1,
G2 y G3. Cada uno de estos grupos incluye las gramáticas del
siguiente, de acuerdo con el siguiente esquema:
Las reglas de producción tienen la forma
La parte izquierda no puede ser la palabra vacía.
En la parte izquierda (u) ha de aparecer algún símbolo no terminal.
Los lenguajes representados por estas gramáticas reciben el nombre de
lenguajes sin restricciones.
Gramáticas tipo 1
Las reglas de producción de esta gramática tienen la forma
Ya que v no puede ser la palabra vacía, se deduce de aquí que este tipo de gramáticas no
pueden tener reglas compresoras. Se admite una excepción en la regla S ::= λ (siendo S el
axioma de la gramática). Como consecuencia se tiene que la palabra vacía pertenece al
lenguaje generado por la gramática sólo si contiene esta regla.
Los lenguajes generados por este tipo de gramáticas se denominan “dependientes del
contexto”.
Gramáticas tipo 2
Las reglas de estas gramáticas se ajustan al siguiente esquema:
Para toda gramática de tipo 2 existe una gramática equivalente desprovista de reglas de
la forma A ::= λ, que generará el mismo lenguaje que la de partida, excepto la palabra
vacía. Si se le añade a la segunda gramática la regla S ::= λ, las gramáticas generarán el
mismo lenguaje.
Por lo tanto, se pueden definir las gramáticas de tipo 2 de una forma más restringida, en el que las reglas de producción tendrán la siguiente forma
Los lenguajes generados por este tipo de gramáticas se denominan independientes de
contexto, ya que la conversión de A en v puede realizarse independientemente del
contexto en que aparezca A.
Gramáticas tipo 3
G1 = ({ 0, 1}, {A, B}, A, { A ::= B1 | 1, B ::= A0})
Gramática lineal por la izquierda que describe el lenguaje:
L1 = { 1, 101, 10101, ... } = {1(01)n | n = 0, 1, 2, ...}
G2 = ({ 0, 1}, {A, B}, A, { A ::= 1B | 1, B ::= 0A})
Gramática lineal derecha que genera el mismo lenguaje que la gramática
anterior.
No hay comentarios:
Publicar un comentario