This is an old revision of the document!
Projection of Automata
Consider alphabet is .
Given a language , define \[
proj(x,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 \}
\]
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 \[
\]
Lemma: