We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

cs.FL

Change to browse by:

cs

References & Citations

DBLP - CS Bibliography

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo

Computer Science > Formal Languages and Automata Theory

Title: A short survey around the pumping lemma for context-free languages

Abstract: Following a seminar the present author gave to an Automata Theory course to computer science students, it will be presented, in a very synthetic and mostly selfcontained way, the principal properties of context free languages (CFL), with particular attention given to the Pumping Lemma (PL), and of grammars which generate them(CFG). We refer to Chomsky and Schutzenberger for the first works about it. What is known in literature as the Iteration Theorem here will be referred to as the Ogden's Lemma in a fully justified way. All definitions not strictly connected with the notion of context freeness will be omitted (we will give precise references for all of them). The symbology used is substantially the classical one, but we will replace some symbols to avoid confusion with those used in logic
Subjects: Formal Languages and Automata Theory (cs.FL)
Cite as: arXiv:2403.15899 [cs.FL]
  (or arXiv:2403.15899v1 [cs.FL] for this version)

Submission history

From: Gabriele Gullà Dr. [view email]
[v1] Sat, 23 Mar 2024 17:53:54 GMT (9kb)

Link back to: arXiv, form interface, contact.