Comments on Monoids Induced by NFAs
Loading...
Date
Authors
Advisors/Reviewers
Further Contributors
Contributing Institutions
Publisher
Journal Title
Journal ISSN
Volume Title
Publisher
License
Quotable link
Abstract
We summarize known results on the transformation monoid of nondeterministic finite automata (NFAs) from semigroup theory. In particular, we list what is known from the literature on the size of monoids induced by NFAs and their (minimal) number of generators - a comprehensive list of these generators is given in the Appendix. It is shown that any language accepted by an n-state NFA has a syntactic monoid of size at most 2^{n^2}. This bound is reachable by the generators of the semigroup B_n of n x n Boolean matrices with the usual matrix multiplication except that we assume 1 + 1 = 1. The number of these generators grows exponentially in n. This is a significant difference to the deterministic case, where three generators suffice to generate all elements of T_n. Moreover, we prove a lower bound for the \nfa-to-\dfa\ conversion using Lambert's W function.Link to publications or other datasets
Description
Notes
Original publication in
Original publication in
Anthology
Collections
URI of original publication
Forschungsdaten
Series
IFIG Research Report;2301