Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their conceptual extension is the non-deterministic finite automata which also have plenty of applications. In this article, we study these models through the lens of succinct data structures where our ultimate goal is to encode these mathematical objects using information-theoretically optimal number of bits along with supporting queries on them efficiently. Towards this goal, we first design a succinct data structure for representing any deterministic finite automaton @math having @math states over a @math -letter alphabet @math using @math bits of space, which can determine, given an input string @math over @math , whether @math accepts @math in @math time, using constant words of working space. When the input deterministic finite automaton is acyclic, not only we can improve the above space-bound significantly to @math bits, we also obtain optimal query time for string acceptance checking. More specifically, using our succinct representation, we can check if a given input string @math can be accepted by the acyclic deterministic finite automaton using time proportional to the length of @math , hence, the optimal query time. We also exhibit a succinct data structure for representing a non-deterministic finite automaton @math having @math states over a @math -letter alphabet @math using @math bits of space, such that given an input string @math , we can decide whether @math accepts @math efficiently in @math time. Finally, we also provide time and space-efficient algorithms for performing several standard operations such as union, intersection, and complement on the languages accepted by deterministic finite automata.
We give asymptotic estimates and some explicit computations for both the number of distinct languages and the number of distinct finite languages over a k-letter alphabet that are accepted by deterministic finite automata (resp. nondeterministic finite automata) with n states.  We present a bijection between the set A"n of deterministic and accessible automata with n states on a k-letters alphabet and some diagrams, which can themselves be represented as partitions of a set of kn+1 elements into n non-empty subsets. This combinatorial construction shows that the asymptotic order of the cardinality of A"n is related to the Stirling number knn . Our bijective approach also yields an efficient random sampler, for the uniform distribution, of automata with n states, its complexity is O(n^3^ ^2), using the framework of Boltzmann samplers.