¿Qué se convierte en gramáticas sensibles al contexto si se permiten $ \ Epsilon $ producciones?

Question

La formulación original de los 3 tipos de gramática restringida de Chomsky, todos incluía la restricción de que el lado derecho de un reemplazo no puede ser $ \ epsilon $ (no-contratación).Esto, sin embargo, puede ser (y generalmente está) levantado para gramáticas regulares y sin contexto (es decir, se les permite tener producciones de la forma $ x \ to \ epsilon $ )) Sin alterar la clase de idiomas generados.

La regla, sin embargo, permanece para gramáticas sensibles al contexto.

Mi pregunta es, dada una gramática con producciones $ \ alfa x \ beta \ to \ alpha \ xi \ beta $ donde $ \ alfa, \ beta, \ xi \ in (n \ taza t) ^ * $ (es decir, una gramática sensible al contexto con $ \ epsilon $ -Rules), ¿qué clase de idiomas describe eso?Los recursivamente enumerables (igual que las gramáticas sin restricciones) o algo más?

Answer 1

Se puede demostrar que las gramáticas sensibles al contexto que describa son equivalentes a simplemente solicitar producciones $ \ alfa \ to to beta $ con $ \ lvert \ alfa \ rvert \ le \ lvert \ beta \ rvert $ .Así que permite producciones $ A \ to \ varepsilon $ solo elimina la restricción en las longitudes, y ha aterrizado en gramáticas sin restricciones.