Linguagem sensível ao contexto
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]
Exemplos[editar | editar código-fonte]
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.
Propriedades[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 determinística arbitrária, é um problema PSPACE-completo.
Teoria da computação[editar | editar código-fonte]
Ver também[editar | editar código-fonte]
Referências[editar | editar código-fonte]
- ↑ 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.
- ↑ 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.
- ↑ Pullum, Geoffrey K. (1983). Context-freeness and the computer processing of human languages. Proc. 21st Annual Meeting of the ACL
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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
- ↑ (Hopcroft, Ullman, 1979); Theorem 9.9 b, p.228
Fontes[editar | editar código-fonte]
- Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.