Computer Science – Formal Languages and Automata Theory
Scientific paper
2009-05-08
Computer Science
Formal Languages and Automata Theory
17 pages. Preprint of an article submitted for consideration in the International Journal of Foundations of Computer Science (
Scientific paper
The simulation of deterministic pushdown automata defined over a one-letter alphabet by finite state automata is investigated from a descriptional complexity point of view. We show that each unary deterministic pushdown automaton of size s can be simulated by a deterministic finite automaton with a number of states that is exponential in s. We prove that this simulation is tight. Furthermore, its cost cannot be reduced even if it is performed by a two-way nondeterministic automaton. We also prove that there are unary languages for which deterministic pushdown automata cannot be exponentially more succinct than finite automata. In order to state this result, we investigate the conversion of deterministic pushdown automata into context-free grammars. We prove that in the unary case the number of variables in the resulting grammar is strictly smaller than the number of variables needed in the case of nonunary alphabets.
No associations
LandOfFree
Deterministic pushdown automata and unary languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Deterministic pushdown automata and unary languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic pushdown automata and unary languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-703574