Linguagem sensível ao contexto

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 (ouDSPACE(O(n))) é definida da mesma forma, exceto por usar uma máquina de Turing deterministica. Claramente LINSPACE é um subconjunto de NLINSPACE, mas não se sabe se LINSPACE=NLINSPACE.[2]

Exemplos[editar | editar código-fonte]

Uma das mais simples linguagens sensíveis ao contexto, mas que não é livre de contexto é L = \{ a^nb^nc^n : n \ge 1 \}: 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.

Propriedades de linguagens sensíveis ao contexto[editar | editar código-fonte]

  • 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 deterministica arbitrária, é um problema PSPACE-completo.

See also[editar | editar código-fonte]

References[editar | editar código-fonte]

  1. Rothe, Jörg (2005), Complexity theory and cryptology, Texts in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, p. 77, ISBN 978-3-540-22147-0 .
  2. Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, 143, Amsterdam: North-Holland Publishing Co., p. 236, ISBN 0-444-50205-X .
  3. Pullum, Geoffrey K. (1983). "Context-freeness and the computer processing of human languages" in Proc. 21st Annual Meeting of the ACL. {{{booktitle}}}. 
  4. Bach, E. (1981). "Discontinuous constituents in generalized categorial grammars". 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. Introduction to Automata Theory, Languages, and Computation. [S.l.]: Addison-Wesley, 1979. ; Exercise 9.10, p.230. In the 2003 edition, the chapter on CSL has been omitted.
  7. doi: 10.1137/0217058
    Esta citação será automaticamente completada em poucos minutos. Você pode furar a fila ou completar manualmente
  8. (Hopcroft, Ullman, 1979); Theorem 9.9 b, p.228
  • Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.

Predefinição:Formal languages and grammars