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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.ipl.2011.03.019 | Information Processing Letters |
Keywords | Field | DocType |
finite automaton,context-free grammar,direct automaton construction,parikh image,simple construction,context-free language,theorem state,regular language,formal language,context free grammar,context free language,formal languages,automata theory | Discrete mathematics,Combinatorics,Context-free language,Nondeterministic finite automaton,Context-free grammar,Formal language,Grammar,Finite-state machine,Regular language,Parikh's theorem,Mathematics | Journal |
Volume | Issue | ISSN |
111 | 12 | Information Processing Letters 111(12) (2011) 614-619 |
Citations | PageRank | References |
30 | 1.04 | 11 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Javier Esparza | 1 | 770 | 60.33 |
Pierre Ganty | 2 | 242 | 20.29 |
Stefan Kiefer | 3 | 345 | 36.87 |
Michael Luttenberger | 4 | 205 | 18.92 |