Parikh's Theorem: A simple and direct automaton construction
arXiv:1006.3825 · doi:10.1016/j.ipl.2011.03.019
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.
12 pages, 3 figures
Cited by in corpus (10)
- Algorithmic Verification of Asynchronous Programs
- Random Language Model
- Parameterized Verification of Asynchronous Shared-Memory Systems
- Approximating Petri Net Reachability Along Context-free Traces
- Bounded-oscillation Pushdown Automata
- Solving non-linear Horn clauses using a linear Horn clause solver
- The Parikh Property for Weighted Context-Free Grammars
- String Solving with Word Equations and Transducers: Towards a Logic for Analysing Mutation XSS (Full Version)
- Decidable Logics Combining Word Equations, Regular Expressions and Length Constraints
- Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent One-Way and Two-Way Deterministic Automata