




Publications  Parikh's theorem: A simple and direct automaton construction





Reference:
Javier Esparza, Pierre Ganty, Stefan Kiefer, and Michael Luttenberger. Parikh's theorem: A simple and direct automaton construction. Information Processing Letters (IPL), 111(12):614–619, 2011.
Abstract:
Parikh's theorem states that the Parikh image of a contextfree language is semilinear or, equivalently, that every contextfree language has the same Parikh image as some regular language. We present a very simple construction that, given a contextfree grammar, produces a finite automaton recognizing such a regular language.
Suggested BibTeX entry:
@article{EGKL11:IPL,
author = {Javier Esparza and Pierre Ganty and Stefan Kiefer and Michael Luttenberger},
journal = {Information Processing Letters (IPL)},
number = {12},
pages = {614619},
title = {Parikh's theorem: A simple and direct automaton construction},
volume = {111},
year = {2011}
}




