Projection of Automata

Consider alphabet $\Sigma$ is $\{0,1\}^V$ .

Given a language $L \subseteq \Sigma^*$ , define

$\begin{equation*} proj(x,L) = \begin{array}[t]{@{}l} \{ a_1 \ldots a_n \mid \exists b_1,\ldots,b_n \in \{0,1\}. a_1[x:=b_1] \ldots a_n[x:=b_n] \in L \} \\ \{ a_1[x:=b_1] \ldots a_n[x:=b_n] \mid b_1,\ldots,b_n \in \{0,1\}, \ a_1 \ldots a_n \in L \} \end{array} \end{equation*}$

Given a finite automaton $A = (\Sigma,Q,\Delta,q_0,F)$ , define projection $proj(x,A)$ as $(\Sigma,Q,\Delta',q_0,F)$ where

$\begin{equation*} \Delta' = \{(q,a,q') \mid \exists b \in \{0,1\}. (q,a[x:=b],q') \in \Delta \} \end{equation*}$

Lemma: $L(proj(x,A)) = proj(x,L(A))$

Given a regular expression $r$ , define $proj(x,r)$ by

$\begin{equation*} \begin{array}{l} proj(x,[F]) = [qe(\exists x.F)] \\ proj(x,r_1 r_2) = proj(x,r_1) proj(x,r_2) \\ proj(x,r^*) = proj(x,r)^* \\ proj(x,r_1 + r_2) = proj(x,r_1) + proj(x,r_2) \end{array} \end{equation*}$

Lemma: $L(proj(x,r)) = proj(x,L(r))$