next up previous contents
Next: Tipo 2 o libres Up: Jerarquía de Chomsky Previous: Tipo 0 o no restringidas   Contents

Tipo 1 o sensibles al contexto.

Este tipo de gramáticas son de la forma $ \alpha\rightarrow \beta$, donde $ \alpha,\beta\in (N\cup \Sigma)^+$ 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 $ \alpha\rightarrow \beta$ entonces $ \mid\beta\mid\geqslant\mid\alpha\mid$. 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 `$ \langle$' y `$ \rangle$' , los cuales acotarán el área de trabajo en la cinta. La producción $ S\rightarrow \varepsilon$ 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