A pumping lemma for random permitting context languages
| Autor: | Andries P. J. van der Walt, Sigrid Ewert |
|---|---|
| Rok vydání: | 2002 |
| Předmět: |
Random context languages
General Computer Science Computer science Context-sensitive grammar computer.software_genre Theoretical Computer Science Indexed language Rule-based machine translation Formal language Programming language Context-free language Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Pumping lemma Regulated rewriting Pumping lemma for regular languages Algebra Tree-adjoining grammar Formal languages Formal grammar TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Extended Affix Grammar Random permitting context Pumping lemma for context-free languages computer Computer Science::Formal Languages and Automata Theory Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 270:959-967 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/s0304-3975(01)00171-2 |
| Popis: | Random context grammars belong to the class of context-free grammars with regulated rewriting. Their productions depend on context that may be randomly distributed in a sentential form. Context is classified as either permitting or forbidding, where permitting context enables the application of a production and forbidding context inhibits it. For random context languages of finite index a generalization of the well-known pumping lemma for context-free languages has been proven. We drop the finite index restriction and concentrate on non-erasing grammars that use permitting context only. We prove a pumping lemma for their languages that generalizes and refines the existing one, and show that these grammars are strictly weaker than the non-erasing random context grammars. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect