Comparisons between some pumping conditions for context-free languages
From MaRDI portal
Publication:4729382
DOI10.1007/BF02088014zbMath0679.68139MaRDI 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
pumping conditions; classic pumping condition of Bar-Hillel; extended Sokolowski condition; generalized Ogden condition
68Q45: Formal languages and automata
Related Items
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