# Unary Quantum Finite State Automata with Control Language
## 2 Preliminaries  
### Formal Languages and Classical Automata  
For the basics of formal language theory, we refer the reader to, e.g., [48]. The set of natural numbers, including zero, is denoted by \(\mathbb{N}\). Given a finite alphabet \(\Sigma\), we let \(\Sigma^{*}\) denote the set of strings (or words) on \(\Sigma\), including the empty string \(\varepsilon\). For a string \(w\in\Sigma^{*}\), we let \(|w|\) denote its length, \(|w|_{\sigma}\) the number of occurrences of the symbol \(\sigma\in\Sigma\) in \(w\), and \(w_{i}\) its \(i\)th symbol. The set of all strings of length \(k\in\mathbb{N}\) on \(\Sigma\) is denoted by \(\Sigma^{k}\), with \(\Sigma^{0}=\{\varepsilon\}\). We let \(\Sigma^{<k}=\bigcup_{j=0}^{k-1}\Sigma^{j}\) and \(\Sigma^{\geq k}=\Sigma^{*}\setminus\Sigma^{<k}\). For a symbol \(\sigma\in\Sigma\) and \(k\in\mathbb{N}\), we let \(\sigma^{k}\) denote the string consisting of \(k\) consecutive copies of the symbol \(\sigma\), with \(\sigma^{0}\) being \(\varepsilon\); we let \(\sigma^{*}=\bigcup_{k\geq 0}\sigma^{k}\), we let \(\sigma^{<k}\) denote the set of strings \(\{\varepsilon,\sigma,\sigma^{2},\ldots,\sigma^{k-1}\}\), and we let \(\sigma^{>k}=\sigma^{*}\setminus\sigma^{<k}\). A language on the alphabet \(\Sigma\) is any subset \(L\subseteq\Sigma^{*}\). A _deterministic finite state automaton_ (dfa) is a 5-tuple \(D=(Q,\,\Sigma,\ q_{\Gamma},\,\delta,\,F)\), where \(Q\) is the finite set of states, \(\Sigma\) the finite input alphabet, \(q_{\Gamma}\in Q\) is the initial state, \(F\subseteq Q\) is the set of accepting states, and \(\delta:Q\times\Sigma\to Q\) is the transition function. By letting \(\delta^{*}:Q\times\Sigma^{*}\to Q\) be the canonical extension of \(\delta\) to \(\Sigma^{*}\) as  
\[\delta^{*}(q,w)= \begin{cases}q&\text{if }w=\varepsilon\\ \delta(\delta^{*}(q,x),\sigma)&\text{if }w=x\sigma,\,\text{for }x\in\Sigma^{*} \text{ and }\sigma\in\Sigma,\end{cases} \]  
we have that \(D\) accepts an input string \(w\in\Sigma^{*}\) if and only \(\delta^{*}(q_{\Gamma},w)\in F\), i.e., whenever the computation of \(D\) on \(w\) ends in an accepting state. The language recognized by \(D\) is the set of strings \(L_{D}=\{w\in\Sigma^{*}|\delta^{*}(q_{\Gamma},w)\in F\}\). A convenient representation of a dfa is by means of its _state diagram_. The state diagram of our dfa\(D\) is the labeled digraph with the state set \(Q\) as the set of vertexes and for which an arc labeled \(\sigma\in\Sigma\) joins the vertex \(p\) to the vertex \(q\) if and only if \(\delta(p,\sigma)=q\). Therefore, the computation of \(D\) on input \(x\in\Sigma^{*}\) can be tracked down in the state diagram by following the path labeled \(x\) from the vertex corresponding to the initial state of \(D\). Such a path ends up in a final state if and only if \(D\) accepts \(x\). Figure 1 displays an example of a dfa state diagram. Another useful description of finite state automata is by their _linear representation_. Let us explain such a representation by considering the dfa \(D\). Suppose \(Q=\{q_{1},\ldots,q_{m}\}\) is its finite set of states. We represent each state \(q_{i}\in Q\) by its characteristic \(m\)-dimensional boolean row vector \(\mathrm{e}_{i}\), which has \(1\) as the \(i\)th component and \(0\) elsewhere. Instead, the transition function \(\delta:Q\times\Sigma\to Q\) is represented by the family \(\{M(\sigma)\}_{\sigma\in\Sigma}\) of \(m\times m\) boolean matrices for which for any \(\sigma\in\Sigma\), the \((i,j)\)th component of \(M(\sigma)\) is \(1\) if and only if \(\delta(q_{i},\sigma)=q_{i}\). Notice that, \(D\) being deterministic, each matrix \(M(\sigma)\) has exactly one \(1\) per each row. The set \(F\subseteq Q\) of accepting states is represented by its characteristic \(m\)-dimensional boolean column vector \(\beta\) having \(1\) at the \(i\)th component if and only if \(q_{i}\in F\).