Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav08:projection_of_automata [2008/05/15 12:39] vkuncak |
sav08:projection_of_automata [2009/04/17 14:00] vkuncak |
||
---|---|---|---|
Line 5: | Line 5: | ||
Given a language $L \subseteq \Sigma^*$, define | Given a language $L \subseteq \Sigma^*$, 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 \} | + | 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} | ||
\] | \] | ||
Line 17: | Line 21: | ||
Given a regular expression $r$, define $proj(x,r)$ by | Given a regular expression $r$, define $proj(x,r)$ by | ||
\[ | \[ | ||
- | \begin{equation*} | + | \begin{array}{l} |
proj(x,[F]) = [qe(\exists x.F)] \\ | proj(x,[F]) = [qe(\exists x.F)] \\ | ||
proj(x,r_1 r_2) = proj(x,r_1) proj(x,r_2) \\ | proj(x,r_1 r_2) = proj(x,r_1) proj(x,r_2) \\ | ||
proj(x,r^*) = proj(x,r)^* \\ | proj(x,r^*) = proj(x,r)^* \\ | ||
proj(x,r_1 + r_2) = proj(x,r_1) + proj(x,r_2) | proj(x,r_1 + r_2) = proj(x,r_1) + proj(x,r_2) | ||
- | \end{equation*} | + | \end{array} |
\] | \] | ||
**Lemma:** $L(proj(x,r)) = proj(x,L(r))$ | **Lemma:** $L(proj(x,r)) = proj(x,L(r))$ | ||