Differences

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

--- sav08:projection_of_automata [2008/05/15 12:32]
vkuncak
+++ sav08:projection_of_automata [2009/04/17 14:00]
vkuncak
@@ Line 1: / Line 1: @@
 ====== Projection of Automata ======
-GIven a [[:Finite state machine|finite automaton]] $A = (\Sigma,Q,\Delta,q_0,F)$ whose alphabet $\Sigma$ is $\{0,1\}^V$, define projection $proj(x,A)$ by changing $\Delta$ into
+Consider alphabet $\Sigma$ is $\{0,1\}^V$.
+Given a language $L \subseteq \Sigma^*$, 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 state machine|finite automaton]] $A = (\Sigma,Q,\Delta,q_0,F)$, define projection $proj(x,A)$ as $(\Sigma,Q,\Delta',q_0,F)$ where
 \[
     \Delta' = \{(q,a,q') \mid \exists b \in \{0,1\}. (q,a[x:=b],q') \in \Delta \}
 \]
+**Lemma:** $L(proj(x,A)) = proj(x,L(A))$
+Given a regular expression $r$, define $proj(x,r)$ 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:** $L(proj(x,r)) = proj(x,L(r))$