A pumping lemma for deterministic context-free languages
From MaRDI portal
Publication:1120293
DOI10.1016/0020-0190(89)90108-7zbMath0672.68041WikidataQ124820415 ScholiaQ124820415MaRDI QIDQ1120293
Publication date: 1989
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(89)90108-7
pumping lemma; iteration theorem; deterministic context-free languages; LR(k) grammars; Greibach normal form; left-part theorems
68Q45: Formal languages and automata
Related Items
Unnamed Item, Pushdown automata with bounded nondeterminism and bounded ambiguity, The computational power of parsing expression grammars, Exact Affine Counter Automata, The effect of jumping modes on various automata models, Formal grammars for turn-bounded deterministic context-free languages, Freezing 1-Tag Systems with States, Measures of nondeterminism for pushdown automata, A pumping lemma for regular closure of prefix-free languages, On the word problem for special monoids, Enhancement of automata with jumping modes, One-Reversal Counter Machines and Multihead Automata: Revisited, A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES
Cites Work