Abstract
We study the problem stated as follows: which values in the range from logn to 2n may be obtained as the state complexity of the reverse of a regular language represented by a minimal deterministic automaton of n states? In the main result of this paper we use an alphabet of size 2n − 2 to show that the entire range of complexities may be produced for any n. This considerably improves an analogous result from the literature that uses an alphabet of size 2n. We also provide some partial results for the case of a binary alphabet.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. In: Fox, J. (ed.) Proceedings of the Symposium on Mathematical Theory of Automata, New York, NY, April 24-26. MRI Symposia Series, vol. 12, pp. 529–561. Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn (1963)
Geffert, V.: Magic numbers in the state hierarchy of finite automata. Inform. Comput. 205, 1652–1670 (2007)
Iwama, K., Kambayashi, Y., Takaki, K.: Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs. Theoret. Comput. Sci. 237, 485–494 (2000)
Iwama, K., Matsuura, A., Paterson, M.: A family of NFAs which need 2n − α deterministic states. Theoret. Comput. Sci. 301, 451–462 (2003)
Jirásková, G.: On the state complexity of complements, stars, and reversals of regular languages. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 431–442. Springer, Heidelberg (2008)
Jirásková, G.: Magic numbers and ternary alphabet. Inter. J. Found. Comput. Sci. 22, 331–344 (2011)
Jirásková, G., Masopust, T.: Complexity in union-free regular languages. Internat. J. Found. Comput. Sci. 22, 1639–1653 (2011)
Jirásková, G., Šebej, J.: Reversal of binary regular languages. Theoret. Comput. Sci. 449, 85–92 (2012)
Leiss, E.: Succinct representation of regular languages by Boolean automata. Theoret. Comput. Sci. 13, 323–330 (1981)
Lupanov, O.B.: A comparison of two types of finite automata. Problemy Kibernetiki 9, 321–326 (1963) (in Russian)
Mirkin, B.G.: On dual automata. Kibernetika (Kiev) 2, 7–10 (1966) (in Russian); English translation: Cybernetics 2, 6–9 (1966)
Rabin, M., Scott, D.: Finite automata and their decision problems. IBM Res. Develop. 3, 114–129 (1959)
Sipser, M.: Introduction to the theory of computation. PWS Publishing Company, Boston (1997)
Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. I, ch. 2, pp. 41–110. Springer, Heidelberg (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Šebej, J. (2013). Reversal on Regular Languages and Descriptional Complexity. In: Jurgensen, H., Reis, R. (eds) Descriptional Complexity of Formal Systems. DCFS 2013. Lecture Notes in Computer Science, vol 8031. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39310-5_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-39310-5_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39309-9
Online ISBN: 978-3-642-39310-5
eBook Packages: Computer ScienceComputer Science (R0)