Lenguaje sensible al contexto

Lenguaje sensible al contexto

En las ciencias de la computación, un lenguaje sensible al contexto es un [[lenguaje formal] que puede ser definido por gramáticas sensibles al contexto. Es uno de los cuatro tipos de gramáticas en la jerarquía de Chomsky, siendo esta gramática la menos frecuente, tanto en la teoría como en la práctica.

Contenido

Propiedades computacionales

Computacionalmente, un lenguaje sensible al contexto es equivalente a una máquina de Turing no determinista linealmente acotada, también llamado Autómata linealmente acotado.Se trata de una máquina de Turing no determinista con una cinta de sólo kn posiciones, donde n es el tamaño de la entrada y k es la constante asociada a la máquina. Esto significa que cada lenguaje formal que puede ser decidido por una máquina es un lenguaje sensible al contexto.

Ejemplos

Un ejemplo de un lenguaje sensible al contexto que no es libre de contexto es
L = {anbncn | n>= 0} no es un lenguaje libre de contexto, pero si es un lenguaje sensible al contexto. Una gramática para L:

Transiciones
S → ε B → ab
S → aSBC bB → bb
CB → HB bC → bc
HB → HC cC → cc
HC → BC











L puede demostrarse como un lenguaje sensible al contexto mediante la construcción de un autómata lineal acotado que acepta L. Se puede demostrar fácilmente que este lenguaje no es ni regular, ni independiente del contexto, por la aplicación del Lema del bombeo. Un ejemplo de un lenguaje recursivo que no es sensible al contexto es cualquier lenguaje recursivo cuya decisión es un problema EXPSPACE-hard, por ejemplo, el conjunto de pares equivalentes de expresiones regulares con exponenciación.

Propiedades

  • La unión, intersección, y concatenación de dos Lenguajes sensibles al contexto es un Lenguaje sensible al contexto.
  • El complemento de un lenguaje sensible al contexto es en si mismo sensible al contexto.
  • Cada gramática libre de contexto es un lenguaje sensible al contexto.
  • La composición de una cadena en un lenguaje definido por una gramática sensible al contexto arbitraria, o por una gramática determinista sensible al contexto arbitraria, es un problema PSPACE-completo.

Véase también

referencias


Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Gramáticas sensibles al contexto — Una gramática sensible al contexto es una gramática formal G = (N, Σ, P, S) tal que todas las producciones P son de la forma: αAβ → αγβ con A en N y α y β en (N U Σ)* y γ en (N U Σ)+, con la posibilidad de la regla lambda S → λ con λ, la cadena… …   Wikipedia Español

  • Lenguaje formalizado — El lenguaje formalizado es un lenguaje sometido a unas «reglas fijas de formación de expresiones y significados». Es una de las características esenciales del lenguaje científico. Incluso hay autores que llegan a opinar que la ciencia en sí misma …   Wikipedia Español

  • Gramática libre de contexto — En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma: V → w Donde V es un símbolo no terminal y w es una cadena de terminales y/o no… …   Wikipedia Español

  • Traducción automática basada en el contexto — o Context Based Machine Translation (CMBT) és una técnica de traducción automática desarrollada por la empresa Meaningful Machines. Hasta hace poco el mundo de la traducción automática se ha desarrollado en dos vías principales: las basadas en… …   Wikipedia Español

  • Autómatas linealmente acotados — Saltar a navegación, búsqueda Un autómata linealmente acotado, abreviadamente LBA (del inglés, Linear Bounded Automaton), es un autómata similar a una máquina de Turing no determinista. Contenido 1 Historia 2 Autómatas lineales …   Wikipedia Español

  • Evidencia (filosofía) — Saltar a navegación, búsqueda Una evidencia (del latín, video, ver) es un conocimiento que se nos aparece intuitivamente de tal manera que podemos afirmar la validez de su contenido, como verdadero, con certeza, sin sombra de duda. Todos tenemos… …   Wikipedia Español

  • Perl — Desarrollador(es) Larry Wall www.perl.org Información general Paradigma multiparadigma, funcional, im …   Wikipedia Español

  • Gramática (autómata) — Una gramática ( G ) desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman… …   Wikipedia Español

  • PSPACE-completo — En teoría de la complejidad computacional, la clase de complejidad PSPACE completo (PSPACE complete en inglés) es el subconjunto de los problemas de decisión en PSPACE y todo problema en PSPACE puede ser reducido a él en tiempo polinomial. Los… …   Wikipedia Español

  • Zenoss — corriendo bajo Linux Desarrollador Zenoss Inc. http://zenoss.com/ …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”