Differences
This shows you the differences between two versions of the page.
|
sav08:projection_of_automata [2009/04/17 14:00] vkuncak |
sav08:projection_of_automata [2015/04/21 17:30] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Projection of Automata ====== | ||
| - | |||
| - | 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))$ | ||