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
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
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
- 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
Predefinição:Teoria da computação
Ver também
Referências
Fontes
- Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
- ↑ Predefinição:Citation.
- ↑ Predefinição:Citation.
- ↑ Predefinição:Citar conferência
- ↑ Bach, E. (1981). "Discontinuous constituents in generalized categorial grammars" Predefinição:Wayback. 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.
- ↑ Predefinição:Citar livro; Exercise 9.10, p.230. In the 2003 edition, the chapter on CSL has been omitted.
- ↑ Predefinição:Citar periódico
- ↑ (Hopcroft, Ullman, 1979); Theorem 9.9 b, p.228