Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
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 context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular language. We present a very simple construction that, given a context-free 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 = {614--619},
    title = {Parikh's theorem: A simple and direct automaton construction},
    volume = {111},
    year = {2011}
}

PDF (217 kB)