LARA

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
sav08:projection_of_automata [2008/05/15 12:32]
vkuncak
sav08:projection_of_automata [2015/04/21 17:30] (current)
Line 1: Line 1:
 ====== Projection of Automata ====== ====== 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 
 +\begin{equation*} 
 +   ​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} 
 +\end{equation*} 
 + 
 +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 
 +\begin{equation*}
     \Delta'​ = \{(q,​a,​q'​) \mid \exists b \in \{0,1\}. (q,​a[x:​=b],​q'​) \in \Delta \}     \Delta'​ = \{(q,​a,​q'​) \mid \exists b \in \{0,1\}. (q,​a[x:​=b],​q'​) \in \Delta \}
-\]+\end{equation*} 
 + 
 +**Lemma:** $L(proj(x,​A)) = proj(x,​L(A))$ 
 + 
 +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{array} 
 +\end{equation*} 
 + 
 +**Lemma:** $L(proj(x,​r)) = proj(x,​L(r))$