Parikh image of pushdown automata

DOI10.1007/978-3-662-55751-8_22zbMATH Open1495.68121arXiv1706.08315OpenAlexW2963717425MaRDI QIDQ1679980FDOQ1679980

Authors: Pierre Ganty, Elena Gutiérrez 

Publication date: 22 November 2017

Abstract: We compare pushdown automata (PDAs for short) against other representations. First, we show that there is a family of PDAs over a unary alphabet with $n$ states and $pgeq2n+4$ stack symbols that accepts one single long word for which every equivalent context-free grammar needs $Omega(n^2(p-2n-4))$ variables. This family shows that the classical algorithm for converting a PDA to an equivalent context-free grammar is optimal even when the alphabet is unary. Moreover, we observe that language equivalence and Parikh equivalence, which ignores the ordering between symbols, coincide for this family. We conclude that, when assuming this weaker equivalence, the conversion algorithm is also optimal. Second, Parikh's theorem motivates the comparison of PDAs against finite state automata. In particular, the same family of unary PDAs gives a lower bound on the number of states of every Parikh-equivalent finite state automaton. Finally, we look into the case of unary deterministic PDAs. We show a new construction converting a unary deterministic PDA into an equivalent context-free grammar that achieves best known bounds.

Full work available at URL: https://arxiv.org/abs/1706.08315

Recommendations

• Converting nondeterministic automata and context-free grammars into Parikh equivalent deterministic automata
• Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
• DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
• Deterministic Pushdown Automata and Unary Languages
• Parikh's theorem and descriptional complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cited In (6)

• Deterministic Pushdown Automata and Unary Languages
• Parikh's theorem and descriptional complexity
• Unary pushdown automata and straight-line programs
• Converting nondeterministic automata and context-free grammars into Parikh equivalent deterministic automata
• On reducing the number of stack symbols in a PDA
• Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata

This page was built for publication: Parikh image of pushdown automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679980)