A Nondeterministic Finite Automaton (NFA) is a tuple \(\mathcal {A}=(\Sigma ,Q,q,\delta , F)\) , where \(\Sigma \)  is a finite alphabet, \(Q\)  is a finite state set with an initial state \(q\) , \(\delta : Q\times \Sigma \rightarrow 2^Q\)  is a transition function, and \(F\)  is an accepting-state set. A run of \(\mathcal {A}\)  over a word \(w=a_1a_2\cdots a_n\)  for some \(n\)  is a state sequence \(r=q_0, q_1,\cdots ,q_n\)  such that \(q_{i+1}\in \delta (q_i,a_i)\)  for \(i\ge 0\) , where \(q_0=q\)  is the initial state. A run is accepting if its final state is accepting. A word is accepted if it has an accepting run. The language of \(\mathcal {A}\) , \(L(\mathcal {A})\) , is the set of all accepted words of \(\mathcal {A}\)  and is called a regular language. A language is also regular if and only if it can be described by a regular expression. We define the size of the automaton \(\mathcal {A}\)  as \(|Q|+|\Sigma |+|\delta |\)  and denote this size by \(|\mathcal {A}|\) .
For NFAs \(\mathcal {A}_1=(\Sigma _1,Q_1, q^1,\delta _1, F_1)\)  and \(\mathcal {A}_2=(\Sigma _2,Q_2,q^2,\delta _2, F_2)\) , we define the product automaton of \(\mathcal {A}_1\)  and \(\mathcal {A}_2\)  as the automaton \(\mathcal {A}_1\times \mathcal {A}_2 = (\Sigma _1\times \Sigma _2,Q_1\times Q_2,q^1\times q^2,\delta , F_1\times F_2)\)  where \((p,p^{\prime })\in \delta ((q,q^{\prime }),(l,l^{\prime }))\)  iff \(p\in \delta _1(q,l)\)  and \(p^{\prime }\in \delta _2(q^{\prime },l^{\prime })\) .
An NFA \(\mathcal {A}\)  is deterministic (called DFA) if for every state \(q\)  and letter \(a\) , \(|\delta (q,a)|\le 1\) . Every NFA can be determinized to a DFA that describes the same language by using the subset construction, possibly with an exponential blow-up [1]}.
It is often more convenient for users to specify regular languages by means of regular expressions, which can be converted to DFA, possibly with an exponential blow-up as well [1]}. We assume here that all regular languages are specified by means of DFAs, as we wish to study the inherent complexity of decomposition.
