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)