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. Título do livro não fornecido. 
  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