Grunsky, Igor; Kurganskyy, Oleksiy; Potapov, Igor On a maximal NFA without mergible states. (English) Zbl 1185.68388 Grigoriev, Dima (ed.) et al., Computer science – theory and applications. First international computer science symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8–12, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34166-8/pbk). Lecture Notes in Computer Science 3967, 202-210 (2006). Summary: In this paper we answer an open question about the exact bound on the maximal number of non-mergible states in nondeterministic finite automaton (NFA). It is shown that the maximal possible number of non-mergible states in a NFA that accepts a given regular language \(L\) is not greater than \(2^{n} - 1\), where \(n\) is the number of states in the minimal deterministic finite automaton that accepts \(L\). Next we show that the bound is reachable by constructing a NFA that have exactly \(2^{n} - 1\) non-mergible states. As a generalization of this result we show that the number of states in a NFA that does not contain a subset of \(k\) mergible states, where \(k > 1\), is bounded by \((k - 1)(2^{n} - 1)\) and the bound is reachable.For the entire collection see [Zbl 1102.68006]. Cited in 1 Document MSC: 68Q45 Formal languages and automata PDFBibTeX XMLCite \textit{I. Grunsky} et al., Lect. Notes Comput. Sci. 3967, 202--210 (2006; Zbl 1185.68388) Full Text: DOI