Gramáticas sensibles al contexto

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 vacía.

Se lo llama sensible al contexto porque α y β determinan la forma que debe tener una cadena que puede ser reemplazada por alguna de las producciones. Una lenguaje formal que puede ser descripto para una gramática sensible al contexto se llama lenguaje sensible al contexto

Definición alternativa

Otra forma de definir las gramáticas sensibles al contexto, es aquella gramática formal con la única restricción que todas las producciones α -> β en P cumplan que |α| ≤ |β| donde |α| es la longitud de α. Se las llama de longitud no decreciente.

Se demuestra que las gramáticas sensibles al contexto, y las de longitud creciente son equivalentes en el sentido que generan los mismos lenguajes, a través de una doble contención, es decir, toda gramática libre de contexto está contenida en las de longitud creciente y viceversa.

Ejemplo

S → abc | aSBc
cB → Bc
bB → bb

Esta gramática genera este lenguaje:  \{ a^n b^n c^n : n \ge 1 \} , que no es libre de contexto. Esto lo sabemos gracias al lema del bombeo. También existe una gramática sensible al contexto para  \{ a^n b^n c^n d^n : n \ge 1 \} , pero es mucho más compleja que la anterior


Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Gramáticas de adjunción de árboles — Las gramáticas de adjunción de árboles (Tree Adjoining Grammars, TAG) son una extensión de las gramáticas formales independientes del contexto y fueron definidas inicialmente por Joshi, Levy y Takahashi en[1] Joshi refina ciertos aspectos en su… …   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

  • 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… …   Wikipedia Español

  • Jerarquía de Chomsky — Noam Chomsky. En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956. Contenido …   Wikipedia Español

  • Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW …   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

  • Jorge Luis Borges — «Borges» redirige aquí. Para otras acepciones, véase Borges (desambiguación). Jorge Luis Borges …   Wikipedia Español

  • Teoría estándar — La teoría estándar fue el primer modelo de gramática generativa propuesto por Noam Chomsky, así como la primera postulación completa de la gramática transformacional. Contenido 1 Componentes del modelo 1.1 El componente sintáctico 1.2 El… …   Wikipedia Español

Compartir el artículo y extractos

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