A pumping lemma for deterministic context-free languages

DOI10.1016/0020-0190(89)90108-7zbMath0672.68041OpenAlexW2009481224WikidataQ124820415 ScholiaQ124820415MaRDI QIDQ1120293

Sheng Yu

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

zbMATH Keywords

pumping lemmaiteration theoremdeterministic context-free languagesLR(k) grammarsGreibach normal formleft-part theorems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (13)

Measures of nondeterminism for pushdown automata ⋮ On the word problem for special monoids ⋮ 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 ⋮ Unnamed Item ⋮ The computational power of parsing expression grammars ⋮ Enhancement of automata with jumping modes ⋮ One-Reversal Counter Machines and Multihead Automata: Revisited ⋮ Pushdown automata with bounded nondeterminism and bounded ambiguity ⋮ A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES ⋮ A pumping lemma for regular closure of prefix-free languages

Cites Work

• Two iteration theorems for the LL(k) languages
• Normal forms of deterministic grammars
• A Formalization of Transition Diagram Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A pumping lemma for deterministic context-free languages