| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427309 | Information Processing Letters | 2011 | 6 Pages |
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.
► We present a very simple automaton construction. ► Our construction takes a context-free grammar and returns a finite automaton. ► Input and output languages have the same Parikh image.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Javier Esparza, Pierre Ganty, Stefan Kiefer, Michael Luttenberger,