This is an old revision of the document!
Projection of Automata
Consider alphabet is .
Given a language , define \[
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}
\]
Given a finite automaton , define projection as where \[
\Delta' = \{(q,a,q') \mid \exists b \in \{0,1\}. (q,a[x:=b],q') \in \Delta \}
\]
Lemma:
Given a regular expression , define by
\[
\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}
\]
Lemma: