# Problems on Finite Automata and the Exponential Time Hypothesis
## 1 Introduction  
Many computer science students will get the impression, at least when taught the basics on the Chomsky hierarchy in their course on Formal Languages, that finite automata are fairly simple devices, and hence it is expected that typical decidability questions on finite automata are easy ones. In fact, for instance, the non-emptiness problem for finite automata is solvable in polynomial time, as well as the uniform word problem. (Even tighter descriptions of the complexities can be given within classical complexity theory, but this is not so important for our presentation here, as we mostly focus on polynomial versus exponential time.) This contrasts to the respective statements for higher levels of the [PERSON] hierarchy. However, this impression is somewhat misled. Finite automata can be also viewed as edge-labeled directed graphs, and as many combinatorial problems are harder on directed graphs compared to undirected ones, it should not come as such a surprise that many interesting questions are actually NP-hard for finite automata. We will study hard problems for finite automata under the perspective of the Exponential Time Hypothesis (ETH) and variants thereof, as surveyed in [1]. In particular, using the famous sparsification lemma [2], ETH implies that there is no \(O(2^{o(n+m)})\) algorithm for SATSIABILITY (SAT) of \(m\)-clause 3 CNF formulae with \(n\) variables, or 3 SAT for short. Notice that for these reductions to work, we have to start out with 3 SAT (i.e., with Boolean formulae in conjunctive normal form where each clause contains (at most) three literals), as it seems unlikely that sparsification also works for general formulae in conjunctive normal form; see [3]. Occasionally, we will also use SETH (Strong ETH); this hypothesis implies that there is no \(O((2-\epsilon)^{n})\) algorithm for solving the satisfiability problem (CNF-)SAT for general Boolean formulae in conjunctive normal form with \(n\) variables for any \(\epsilon>0\). Recall that the \(O^{*}\) notation suppresses polynomial factors, measured in the overall input length. This notation is common in exact exponential-time algorithms, as well as in parameterizedalgorithms, as it allows to focus on the decisive exponential part of the running time. We refer the reader to textbooks like [4; 5; 6]. Let us now briefly yet more thoroughly discuss the objects and questions that we are going to study in the following. Mostly, we consider finite-state automata that read input words over the input alphabet \(\Sigma\) one-way, from left to right, and they accept when entering a final state upon reading the last letter of the word. We only consider deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs). The language (set of words) accepted by a given automaton \(A\) is denoted by \(L(A)\). For these classical devices, both variants of the membership problem are solvable in polynomial time and they are therefore irrelevant to the complexity studies we are going to undertake. Rather, we are going to study the following three problems. In each case, we clarify the natural parameters that come with the input, as we will show algorithms whose running times depend on these parameters, and, more importantly, we will prove lower bounds for such algorithms based on (S)ETH. **Problem 1** (Universality). : _Given an automaton \(A\) with input alphabet \(\Sigma\), is \(L(A)=\Sigma\)*? Parameters are the number \(q\) of states of \(A\) and the size of \(\Sigma\)._  
**Problem 2** (Equivalence). : _Given two automata \(A_{1},A_{2}\) with input alphabet \(\Sigma\), is \(L(A_{1})=L(A_{2})\)? Parameters are an upper bound \(q\) on the number of states of \(A_{1},A_{2}\) and the size of \(\Sigma\)._  
Clearly, Universality reduces to Equivalence by choosing the automaton \(A_{2}\) such that \(L(A_{2})=\Sigma\)*. Also, all these problems can be solved by computing the equivalent (minimal) deterministic automata, which requires time \(O\)*\((2^{q})\).