Linguagem indexada
Linguagens indexadas são uma classe de linguagens formais descoberta por Alfred Aho;[1] elas são descritas por gramáticas indexadas e podem ser reconhecidas por autômatos com pilhas aninhados.[2]
Linguagens indexadas são um subconjunto próprio de linguagens sensíveis ao contexto.[1] Elas qualificam uma família abstrata de linguagens (Além disso, um AFL cheio) e satisfazem muitas propriedades de fechamento. No entanto, elas não são fechadas sob interseção nem complemento.[1]
A classe de linguagens indexadas tem importância prática no processamento de linguagens naturais como computacionalmente acessível, generalização das linguagens livre-do-contexto, desde que gramáticas indexadas possam descrever muitas das restrições não locais ocorrendo em linguagem naturais.
Gerald Gazdar (1988)[3] e Vijay-Shanker (1987)[4] introduziram a classe da linguagem moderadamente sensível ao contexto agora conhecida como gramáticas linearmente indexadas (LIG).[5] Gramáticas linearmente indexadas tem restrições adicionais relativas a IG. LIGs são fracamente equivalentes(geram a mesma classe de linguagem) como gramáticas árvore-adjacentes.[6]
Exemplos editar
As seguintes linguagens são indexadas, mas não são livres-do-contexto:
Essas duas linguagens também são indexadas, mas não são nem ao menos moderadamente sensíveis a contexto sobre a caracterização de Gazdar:
Por outro lado, a seguinte linguagem não é indexada:[7]
Propriedades editar
Hopcroft e Ullman tendem a considerar linguagens indexadas como uma classe natural, visto que elas são geradas por vários formalismos, tais como:[9]
- Gramática indexada de Aho[1]
- Automato com pilha de Aho[10]
- Macrogramáticas de Fischer[11]
- Caracterização algébrica de Maibaum[12]
Hayashi[13] generalizou o lema do bombeamento para linguagens indexadas. Reciprocamente, Gilman[7][14] deu um "lema da diminuição" para as linguagens indexadas.
Ver também editar
Referências
- ↑ a b c d Aho, Alfred (1968). «Indexed grammars—an extension of context-free grammars». Journal of the ACM. 15 (4): 647–671. doi:10.1145/321479.321488
- ↑ a b c Partee, Barbara; Alice ter Meulen; Robert E. Wall (1990). Mathematical Methods in Linguistics. [S.l.]: Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4
- ↑ a b c Gazdar, Gerald (1988). «Applicability of Indexed Grammars to Natural Languages». In: U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. [S.l.: s.n.] pp. 69–94
- ↑ http://search.proquest.com/docview/303610666
- ↑ Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. [S.l.]: Springer Science & Business Media. p. 31. ISBN 978-3-642-14846-0
- ↑ Laura Kallmeyer (16 de agosto de 2010). Parsing Beyond Context-Free Grammars. [S.l.]: Springer Science & Business Media. p. 32. ISBN 978-3-642-14846-0
- ↑ a b Gilman, Robert H. (30 de agosto de 1996). «A shrinking lemma for indexed languages». Theoretical Computer Science. 163 (1–2): 277-281. doi:10.1016/0304-3975(96)00244-7
- ↑ Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. [S.l.]: Addison-Wesley. p. 390. ISBN 0-201-02988-X
- ↑ Introduction to automata theory, languages, and computation,[8] Bibliographic notes, p.394-395
- ↑ Alfred Aho (1969). «Nested Stack Automata». Journal of the ACM. 16 (3): 383-406. doi:10.1145/321526.321529
- ↑ Michael J. Fischer (1968). «Grammars with Macro-Like Productions». Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT). [S.l.: s.n.] pp. 131–142
- ↑ T.S.E. Maibaum (1974). «A Generalized Approach to Formal Languages» (PDF). J. Computer and System Sciences. 8 (3): 409-439. doi:10.1016/s0022-0000(74)80031-0
- ↑ T. Hayashi (1973). «On Derivation Trees of Indexed Grammars - An Extension of the uvxyz Theorem». Research Institute for Mathematical Sciences. Publication of the Research Institute for Mathematical Sciences. 9 (1): 61-92. doi:10.2977/prims/1195192738
- ↑ Robert H. Gilman (setembro de 1995). «A Shrinking Lemma for Indexed Languages»