Dissemin is shutting down on January 1st, 2025

Links

Tools

Export citation

Search in Google Scholar

A Proof of the Pumping Lemma for Context-Free Languages Through Pushdown Automata

Journal article published in 2012 by Antoine Amarilli ORCID, Marc Jeanmougin ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown

Abstract

The pumping lemma for context-free languages is a result about pushdown automata which is strikingly similar to the well-known pumping lemma for regular languages. However, though the lemma for regular languages is simply proved by using the pigeonhole principle on deterministic automata, the lemma for pushdown automata is proven through an equivalence with context-free languages and through the more powerful Ogden's lemma. We present here a proof of the pumping lemma for context-free languages which relies on pushdown automata instead of context-free grammars. ; Comment: Corrected a typo in a definition, added related work, added acknowledgement, added note about proving Ogden's lemma