Comparisons between some pumping conditions for context-free languages

DOI10.1007/BF02088014zbMath0679.68139OpenAlexW2027422726MaRDI QIDQ4729382

Giora Slutzki, Rattikorn Hewett

Publication date: 1989

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02088014

zbMATH Keywords

pumping conditionsclassic pumping condition of Bar-Hillelextended Sokolowski conditiongeneralized Ogden condition

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Comparisons of Parikh's condition to other conditions for context-free languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the sufficiency of Sokolowski's criterion for context-free languages
• A strong pumping lemma for context-free languages
• A method for proving programming languages non context-free
• Optimization of LR(k) parsers
• Linearity is polynomially decidable for realtime pushdown store automata
• Ogden's lemma for nonterminal bounded languages
• Extensions of sokolowski's theorem to prove languages are not context free or not regular
• A Generalization of Ogden's Lemma
• On Context-Free Languages
• A helpful result for proving inherent ambiguity