Lenguaje sensible al contexto

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En la teoría del lenguaje formal, un lenguaje sensible al contexto es un lenguaje que se puede definir mediante una gramática sensible al contexto (y de manera equivalente mediante una gramática no contractiva). Sensible al contexto es uno de los cuatro tipos de gramáticas en la jerarquía de Chomsky.

Propiedades computacionales

Computationally, a context-sensible language is equivalent to a linear bounded nondeterministic Turing machine, also called a linear bounded automaton. Esa es una máquina Turing no determinista con una cinta de sólo ${displaystyle kn}$ células, donde $n$ es el tamaño de la entrada y $k$ es una constante asociada con la máquina. Esto significa que cada lenguaje formal que pueda decidirse por tal máquina es un lenguaje sensible al contexto, y cada lenguaje sensible al contexto puede ser decidido por tal máquina.

Este conjunto de idiomas también se conoce como NLINSPACE o NSPACE(O(n)), porque se pueden aceptar utilizando el espacio lineal en una máquina de Turing no determinista. La clase LINSPACE (o DSPACE(O(n))) se define de la misma manera, excepto que se usa un determinista Máquina de Turing. Claramente, LINSPACE es un subconjunto de NLINSPACE, pero no se sabe si LINSPACE=NLINSPACE.

Ejemplos

Uno de los idiomas más simples y sensibles al contexto pero no sin contexto es $L={a^{n}b^{n}c^{n}:ngeq 1}$ : el lenguaje de todas las cuerdas consistentes en $n$ ocurrencias del símbolo "a", entonces $n$ "b"'s, entonces $n$ "c" (abc, aabbcc, aaabbbccc, etc.). Un superconjunto de este lenguaje, llamado el idioma Bach, se define como el conjunto de todas las cadenas donde "a", "b" y "c" (o cualquier otro conjunto de tres símbolos) ocurre igualmente a menudo (aabccb, baabcaccb, etc.) y también es sensible al contexto.

Se puede demostrar que

$L$ es un lenguaje sensible al contexto mediante la construcción de un autómata acotado lineal que acepta $L$ . Se puede demostrar fácilmente que el lenguaje no es regular ni está libre de contexto aplicando los lemas de bombeo respectivos para cada una de las clases de lenguaje a $L$ .

Del mismo modo:

${displaystyle L_{Cross}={a^{m}b^{n}c^{m}d^{n}:mgeq 1,ngeq 1}}$ es otro lenguaje sensible al contexto; la gramática correspondiente sensible al contexto se puede proyectar fácilmente comenzando con dos gramáticas libres de contexto generando formas sententiales en los formatos ${displaystyle a^{m}C^{m}}$ y ${displaystyle B^{n}d^{n}}$ y luego complementarlos con una producción de permutación como ${displaystyle CBrightarrow BC}$ , un nuevo símbolo inicial y azúcar sintáctica estándar.

${displaystyle L_{MUL3}={a^{m}b^{n}c^{mn}:mgeq 1,ngeq 1}}$ es otro lenguaje sensible al contexto (el "3" en nombre de este lenguaje está destinado a significar un alfabeto ternario); es decir, la operación "producto" define un lenguaje sensible al contexto (pero la "sum" define sólo un lenguaje libre de contexto como la gramática ${displaystyle Srightarrow aSc|R}$ y ${displaystyle Rrightarrow bRc|bc}$ muestra). Debido a la propiedad comunicativa del producto, la gramática más intuitiva ${displaystyle L_{MUL3}}$ es ambiguo. Este problema se puede evitar considerando una definición más restrictiva del idioma, por ejemplo. $<math alttext="{displaystyle L_{ORDMUL3}={a^{m}b^{n}c^{mn}:1<mLORDMUL3={}ambncmn:1.m.n}{displaystyle ¿Qué?<img alt="{displaystyle L_{ORDMUL3}={a^{m}b^{n}c^{mn}:1<m$ . Esto puede ser especializado $1,n>1}}" xmlns="http://www.w3.org/1998/Math/MathML">LMUL1={}amn:m■1,n■1}{displaystyle - ¿Qué?1,n>1}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7369cbadfb66a282f1ff3b77d5622864da5b4957" style="vertical-align: -0.838ex; width:30.986ex; height:2.843ex;"/>$ y, desde esto, hasta $1}}" xmlns="http://www.w3.org/1998/Math/MathML">Lm2={}am2:m■1}{displaystyle ¿Qué?1}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/254a359cd69d99771a7e15ae71e12ea024b7ac87" style="vertical-align: -0.838ex; width:21.488ex; height:3.509ex;"/>$ , $1}}" xmlns="http://www.w3.org/1998/Math/MathML">Lm3={}am3:m■1}{displaystyle ¿Qué?1}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9f184d8d23aa6d2a527714259cac7e99674f8948" style="vertical-align: -0.838ex; width:21.488ex; height:3.509ex;"/>$ , etc.

${displaystyle L_{REP}={w^{|w|}:win Sigma ^{*}}}$ es un lenguaje sensible al contexto. La gramática correspondiente sensible al contexto se puede obtener como una generalización de las gramáticas sensibles al contexto para ${displaystyle L_{Square}={w^{2}:win Sigma ^{*}}}$ , ${displaystyle L_{Cube}={w^{3}:win Sigma ^{*}}}$ , etc.

${displaystyle L_{EXP}={a^{2^{n}}:ngeq 1}}$ es un lenguaje sensible al contexto.

${displaystyle L_{PRIMES2}={w:|w|{mbox{ is prime }}}}$ es un lenguaje sensible al contexto (el "2" en el nombre de este idioma está destinado a significar un alfabeto binario). Esto fue probado por Hartmanis utilizando lemmas de bombeo para lenguajes regulares y sin contexto sobre un alfabeto binario y, después de eso, dibujando un automatón multitape lineal atado aceptando ${displaystyle L_{PRIMES2}}$ .

${displaystyle L_{PRIMES1}={a^{p}:p{mbox{ is prime }}}}$ es un lenguaje sensible al contexto (el "1" en el nombre de este idioma está destinado a significar un alfabeto no deseado). Esto fue acreditado por A. Salomaa a Matti Soittola por medio de un autómata ligado lineal sobre un alfabeto no deseado (páginas 213-214, ejercicio 6.8) y también a Marti Penttonen por medio de una gramática sensible al contexto también sobre un alfabeto no deseado (ver: Lenguas formales por A. Salomaa, página 14, Ejemplo 2.5).

Un ejemplo de lenguaje recursivo que no es sensible al contexto es cualquier lenguaje recursivo cuya decisión es un problema difícil de EXPSPACE, digamos, el conjunto de pares de expresiones regulares equivalentes con exponenciación.

Propiedades de los lenguajes sensibles al contexto

La unión, intersección, concatenación de dos idiomas sensibles al contexto es sensible al contexto, también el Kleene más un lenguaje sensible al contexto es sensible al contexto.
El complemento de un lenguaje sensible al contexto es en sí mismo un resultado sensible al contexto conocido como el teorema Immerman-Szelepcsényi.
La pertenencia a una cadena en un idioma definido por una gramática arbitraria sensible al contexto, o por una gramática arbitraria determinista sensible al contexto, es un problema completo de PSPACE.

Contenido relacionado

Más resultados...