Next: Tipo 2 o libres
Up: Jerarquía de Chomsky
Previous: Tipo 0 o no restringidas
Contents
Este tipo de gramáticas son de la forma
, donde
y la longitud de una cadena generada debe ser mayor o igual a la longitud de la cadena de la cual deriva, esto es, si
entonces
. Estas gramáticas generan lenguajes, aceptados por los atómatas linealmente acotados, que son una variación de una máquina de Turing no determinista, solo que se le agrega al alfabeto de la cinta los signos delimitadores `' y `' , los cuales acotarán el área de trabajo en la cinta. La producción
es válida solo si la palabra vacía es incluida en el lenguaje.
Hay que recordar que cualquier variación de un máquina de Turing puede ser emulada por la máquina de la definición original.
Pablo Gerardo Padilla Beltran
2005-10-21