Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
Ist Teil von
Information and computation, 2013-07, Vol.228-229, p.1-15
Ort / Verlag
Elsevier Inc
Erscheinungsjahr
2013
Quelle
Free E-Journal (出版社公開部分のみ)
Beschreibungen/Notizen
We investigate the conversion of one-way nondeterministic finite automata and context-free grammars into Parikh equivalent one-way and two-way deterministic finite automata, from a descriptional complexity point of view.
We prove that for each one-way nondeterministic automaton with n states there exist Parikh equivalent one-way and two-way deterministic automata with eO(n⋅lnn) and p(n) states, respectively, where p(n) is a polynomial. Furthermore, these costs are tight. In contrast, if all the words accepted by the given automaton contain at least two different letters, then a Parikh equivalent one-way deterministic automaton with a polynomial number of states can be found.
Concerning context-free grammars, we prove that for each grammar in Chomsky normal form with h variables there exist Parikh equivalent one-way and two-way deterministic automata with 2O(h2) and 2O(h) states, respectively. Even these bounds are tight.