We investigate the conversion of nondeterministic finite automata and context-free grammars into Parikh equivalent deterministic finite automata, from a descriptional complexity point of view. We prove that for each nondeterministic automaton with n states there exists a Parikh equivalent deterministic automaton with eO( √n·ln n) states. Furthermore, this cost is tight. In contrast, if all the strings accepted by the given automaton contain at least two different letters, then a Parikh equivalent 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 n variables there exists a Parikh equivalent deterministic automaton with 2O(n2) states. Even this bound is tight.

Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata / G.J. Lavado, G. Pighizzini, S. Seki. ((Intervento presentato al 13. convegno Italian Conference on Theoretical Computer Science tenutosi a Varese nel 2012.

Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata

G.J. Lavado
Primo
;
G. Pighizzini
Secondo
;
2012

Abstract

We investigate the conversion of nondeterministic finite automata and context-free grammars into Parikh equivalent deterministic finite automata, from a descriptional complexity point of view. We prove that for each nondeterministic automaton with n states there exists a Parikh equivalent deterministic automaton with eO( √n·ln n) states. Furthermore, this cost is tight. In contrast, if all the strings accepted by the given automaton contain at least two different letters, then a Parikh equivalent 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 n variables there exists a Parikh equivalent deterministic automaton with 2O(n2) states. Even this bound is tight.
20-set-2012
Finite automaton; Context-free grammar; Parikh's Theorem; Descriptional complexity; Semilinear set; Parikh equivalence
Settore INF/01 - Informatica
Dipartimento di di Scienze Teoriche e Applicate
Università dell'Insubria
Italian Chapter of the European Association of Theoretical Computer Science (EATCS)
http://ictcs.di.unimi.it
Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata / G.J. Lavado, G. Pighizzini, S. Seki. ((Intervento presentato al 13. convegno Italian Conference on Theoretical Computer Science tenutosi a Varese nel 2012.
Conference Object
File in questo prodotto:
File Dimensione Formato  
abstract_parikh_ICTCS2012.pdf

accesso aperto

Descrizione: extended abstract
Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 233.55 kB
Formato Adobe PDF
233.55 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/482850
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact