×

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].

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI