Differences

This shows you the differences between two versions of the page.

--- 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
 \[
-   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
 \[
-\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{equation*}
+\end{array}
 \]
 **Lemma:** $L(proj(x,r)) = proj(x,L(r))$