Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | Next revision Both sides next revision | ||
reachable_pushdown_configurations_are_regular [2007/05/30 23:33] vkuncak |
reachable_pushdown_configurations_are_regular [2007/05/31 00:07] vkuncak |
||
---|---|---|---|
Line 21: | Line 21: | ||
We represent the sets of reachable states as an automaton. Let $P = \{ p^1,\ldots,p^m\}$. We represent a set $T$ of pushdown configurations, which are elements of $P \times \Gamma^*$, by splitting it according to $P$, so that $T = \{(p^i,w) \mid w \in L^i$. Therefore, $L^i \substeq \Gamma^*$ represents the set of possible values for stacks when the automaton is in the state $p^i$. We define each $L^i$ as the language accepted by a finite state machine. It turns out that we can use the same set of states for machines representing different $L^i$, all we need to introduce are different initial states. This leads to the notion of multi-automaton, which is just an ordinary non-deterministic [[finite state machine]], but with a //set// of initial states instead of just one initial state. Specifically, we define a multi-automaton for the pushdown system with control states $P$ as ${\cal A} = (\Gamma,Q,\delta,I,F)$ where the input alphabet $\Gamma$ for the finite state machine is the stack alphabet of the pushdown system, $Q$ is some finite set of states of the multi-automaton, $\delta \subseteq Q \times \Gamma \times Q$, $F \subseteq Q$. The set $I = \{ s^1,\ldots,s^m \}$ of initial states has one initial state for each control state of the pushdown system. | We represent the sets of reachable states as an automaton. Let $P = \{ p^1,\ldots,p^m\}$. We represent a set $T$ of pushdown configurations, which are elements of $P \times \Gamma^*$, by splitting it according to $P$, so that $T = \{(p^i,w) \mid w \in L^i$. Therefore, $L^i \substeq \Gamma^*$ represents the set of possible values for stacks when the automaton is in the state $p^i$. We define each $L^i$ as the language accepted by a finite state machine. It turns out that we can use the same set of states for machines representing different $L^i$, all we need to introduce are different initial states. This leads to the notion of multi-automaton, which is just an ordinary non-deterministic [[finite state machine]], but with a //set// of initial states instead of just one initial state. Specifically, we define a multi-automaton for the pushdown system with control states $P$ as ${\cal A} = (\Gamma,Q,\delta,I,F)$ where the input alphabet $\Gamma$ for the finite state machine is the stack alphabet of the pushdown system, $Q$ is some finite set of states of the multi-automaton, $\delta \subseteq Q \times \Gamma \times Q$, $F \subseteq Q$. The set $I = \{ s^1,\ldots,s^m \}$ of initial states has one initial state for each control state of the pushdown system. | ||
+ | === Computing pre-image of a regular set === | ||
+ | |||
+ | Given a set of $T \subseteq P \times \Gamma^*$ of pushdown system configurations, its pre-image is the set | ||
+ | \begin{equation*} | ||
+ | \mbox{pre}(T) = \{ (p^j,\gamma w') \mid ((p^j, \gamma),(p^k,w)) \in \Delta\ \land\ (p^k,w w') \in T \} | ||
+ | \end{equation*} | ||
+ | which contains all states that can lead to a state in $T$. Given the representation of $T$ using a family of sets $L^i$, we can define the corresponding pre-image computation of $L^i$ by | ||
+ | \begin{equation*} | ||
+ | \mbox{pre}(L^j) = \{ \gamma w' \mid ((p^j, \gamma),(p^k,w w')) \in \Delta\ \land\ w w' \in L^k \} | ||
+ | \end{equation*} | ||