RAIRO-Theor. Inf. Appl.
Volume 40, Number 3, July-September 2006Word Avoidability Complexity And Morphisms (WACAM)
|Page(s)||485 - 499|
|Published online||18 October 2006|
Deterministic blow-ups of minimal NFA's
Mathematical Institute, Slovak Academy of Sciences, Grešákova 6, 040 01 Košice, Slovakia;
Accepted: 10 February 2005
The paper treats the question whether there always exists a minimal nondeterministic finite automaton of n states whose equivalent minimal deterministic finite automaton has α states for any integers n and α with n ≤ α ≤ 2n. Partial answers to this question were given by Iwama, Kambayashi, and Takaki (2000) and by Iwama, Matsuura, and Paterson (2003). In the present paper, the question is completely solved by presenting appropriate automata for all values of n and α. However, in order to give an explicit construction of the automata, we increase the input alphabet to exponential sizes. Then we prove that 2n letters would be sufficient but we describe the related automata only implicitly. In the last section, we investigate the above question for automata over binary and unary alphabets.
Mathematics Subject Classification: 68Q45 / 68Q19
Key words: Regular languages / deterministic finite automata / nondeterministic finite automata / state complexity.
© EDP Sciences, 2006
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.