Wikipédia

Linguagem sensível ao contexto: diferenças entre revisões

Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
m traduzindo nome/parâmetro nas citações usando script
Linha 5:
 
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. <ref> {{citation
| lastúltimo = Rothe | firstprimeiro = Jörg
| isbn = 978-3-540-22147-0
| location local= Berlin
| mr = 2164257
| page página= 77
| publisher publicado= Springer-Verlag
| series = Texts in Theoretical Computer Science. An EATCS Series
| title título= Complexity theory and cryptology
| year ano= 2005}}.</ref> A classe '''LINSPACE''' (ou'''DSPACE'''(''O''(''n''))) é definida da mesma forma, exceto por usar uma máquina de Turing [[Máquina_de_estados_finitos_determinística|deterministica]]. Claramente '''LINSPACE''' é um subconjunto de '''NLINSPACE''', mas não se sabe se '''LINSPACE'''='''NLINSPACE'''.<ref>{{citation
| lastúltimo = Odifreddi | firstprimeiro = P. G.
| isbn = 0-444-50205-X
| location local= Amsterdam
| mr = 1718169
| page página= 236
| publisher publicado= North-Holland Publishing Co.
| series = Studies in Logic and the Foundations of Mathematics
| title título= Classical recursion theory. Vol. II
| volume = 143
| year ano= 1999}}.</ref>
 
== Exemplos ==<!-- [[Bach language]] redirects here -->
 
Uma das mais simples linguagens sensíveis ao contexto, mas que não é livre de contexto é <math>L = \{ a^nb^nc^n : n \ge 1 \}</math>: 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,<ref>{{cite conferencecitar conferência|lastúltimo =Pullum |firstprimeiro =Geoffrey K. |yearano=1983 |titletítulo=Context-freeness and the computer processing of human languages |conferenceconferencia=Proc. 21st Annual Meeting of the [[Association for Computational Linguistics|ACL]] |datedata=1983}}</ref> é 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.<ref>Bach, E. (1981). [http://people.umass.edu/ebach/papers/nels11.htm "Discontinuous constituents in generalized categorial grammars"]. ''NELS'', vol. 11, pp.&nbsp;1&ndash;12.</ref><ref>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.</ref>
 
Outro exemplo de linguagem sensível ao contexto que não é livre de contexto é ''L'' = { ''a<sup>p</sup>'' : ''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 [[linguagem regular|regular]] e nem [[linguagem livre de contexto|livre de contexto]] aplicando os respectivos [[Lema do bombeamento|lemas de bombeamento]] para cada classe de linguagem para ''L''.
Linha 34:
== Propriedades ==
 
* A união, interseção, concatenação e [[Fecho de Kleene|operação estrela/fecho de kleene]] de duas as linguagens sensíveis ao contexto é uma linguagem sensível ao contexto.<ref>{{citecitar booklivro|authorsautores=John E. Hopcroft, Jeffrey D. Ullman|titletítulo=Introduction to Automata Theory, Languages, and Computation|publisherpublicado=Addison-Wesley|yearano=1979}}; Exercise 9.10, p.230. In the 2003 edition, the chapter on CSL has been omitted.</ref>
* O complemento de uma linguagem sensível ao contexto é em si sensível ao contexto. <ref>{{Citar periódico|titulo = Nondeterministic Space is Closed under Complementation|url = http://epubs.siam.org/doi/abs/10.1137/0217058|jornal = SIAM Journal on Computing|data = 1988-10-01|issn = 0097-5397|paginas = 935-938|volume = 17|numero = 5|doi = 10.1137/0217058|primeiro = N.|ultimo = Immerman}}</ref>
* Toda gramática [[gramática livre de contexto|livre de contexto]] que não contém a String vazia é sensível ao contexto.<ref>(Hopcroft, Ullman, 1979); Theorem 9.9 b, p.228</ref>
Obtida de "https://pt.wikipedia.org/wiki/Linguagem_sensível_ao_contexto"