Linguagem sensível ao contexto – Wikipédia, a enciclopédia livre

Na Ciência da computação teórica, a 'linguagem sensível ao contexto' é uma linguagem formal que pode ser definida por uma Gramática sensível ao contexto. Esse é um dos quatro tipos de gramáticas na hierarquia de Chomsky.

Propriedades computacionais

[editar | editar código-fonte]

Computacionalmente, uma linguagem sensível ao contexto é equivalente a uma máquina de Turing não determinística linearmente limitada, também chamado de autômato linearmente limitado. Ela é uma máquina de Turing não determinística com uma fita de apenas kn 'células', onde 'n' é o tamanho da entrada e 'k' é uma constante associada com a máquina. Isto significa que toda linguagem formal que pode ser decidida por uma máquina desse tipo é uma linguagem sensível ao contexto, e cada linguagem sensível ao contexto pode ser decidida por uma máquina desse tipo.

Este conjunto de linguagens também é conhecido como 'NLINSPACE' ou 'NSPACE' (O '(' 'n' ')), porque eles podem ser aceitos usando o espaço linear em uma máquina de Turing não determinística.[1] A classe LINSPACE (ou DSPACE(O(n))) é definida da mesma forma, exceto por usar uma máquina de Turing determinística. Claramente LINSPACE é um subconjunto de NLINSPACE, mas não se sabe se LINSPACE=NLINSPACE.[2]

Uma das mais simples linguagens sensíveis ao contexto, mas que não é livre de contexto é : A linguagem de todas as cadeias consistindo em n ocorrências do símbolo "a", e n "b"'s, e n "c"'s (abc, aabbcc, aaabbbccc, etc.). Um superconjunto dessa linguagem, chamada de linguagem de Bach,[3] é definido como o conjunto de todas as cadeias onde "a", "b" e "c" (ou qualquer outro conjunto de símbolos) ocorrem com a mesma frequência (aabccb, baabcaccb, etc.) e isso também é sensível ao contexto.[4][5]

Outro exemplo de linguagem sensível ao contexto que não é livre de contexto é L = { ap : p é um número primo }. Podemos demonstrar que L é sensível ao contexto construindo um autômato limitado linearmente que aceita L. Podemos demonstrar facilmente que a linguagem não é nem regular e nem livre de contexto aplicando os respectivos lemas de bombeamento para cada classe de linguagem para L. Um exemplo de linguagem recursiva que não é sensível ao contexto é qualquer linguagem recursiva cuja decisão é um problema EXPSPACE-HARD, como exemplo o conjunto de pares de expressões regulares são equivalentes com a exponenciação.

  • A união, interseção, concatenação e operação estrela/fecho de kleene de duas as linguagens sensíveis ao contexto é uma linguagem sensível ao contexto.[6]
  • O complemento de uma linguagem sensível ao contexto é em si sensível ao contexto.[7]
  • Toda gramática livre de contexto que não contém a String vazia é sensível ao contexto.[8]
  • A composição de uma cadeia em uma linguagem definida arbitrariamente por uma gramática sensível ao contexto, ou por uma gramática sensível ao contexto determinística arbitrária, é um problema PSPACE-completo.

Teoria da computação

[editar | editar código-fonte]
Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito


  1. Rothe, Jörg (2005), Complexity theory and cryptology, ISBN 978-3-540-22147-0, Texts in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, p. 77, MR 2164257 .
  2. Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, ISBN 0-444-50205-X, Studies in Logic and the Foundations of Mathematics, 143, Amsterdam: North-Holland Publishing Co., p. 236, MR 1718169 .
  3. Pullum, Geoffrey K. (1983). Context-freeness and the computer processing of human languages. Proc. 21st Annual Meeting of the ACL 
  4. Bach, E. (1981). "Discontinuous constituents in generalized categorial grammars" Arquivado em 21 de janeiro de 2014, no Wayback Machine.. NELS, vol. 11, pp. 1–12.
  5. Joshi, A.; Vijay-Shanker, K.; and Weir, D. (1991). "The convergence of mildly context-sensitive grammar formalisms". In: Sells, P., Shieber, S.M. and Wasow, T. (Editors). Foundational Issues in Natural Language Processing. Cambridge MA: Bradford.
  6. John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. [S.l.]: Addison-Wesley ; Exercise 9.10, p.230. In the 2003 edition, the chapter on CSL has been omitted.
  7. Immerman, N. (1 de outubro de 1988). «Nondeterministic Space is Closed under Complementation». SIAM Journal on Computing. 17 (5): 935-938. ISSN 0097-5397. doi:10.1137/0217058 
  8. (Hopcroft, Ullman, 1979); Theorem 9.9 b, p.228
  • Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.