Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426258 | Information and Computation | 2008 | 15 Pages |
Abstract
The paper proves a pumping lemma for a certain subclass of mildly context-sensitive languages, the one defined by commutation-augmented pregroup grammars; in addition, an automaton equivalent to such grammars is introduced, augmenting push-down automata by cancellation in the bottom of its stack.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics