Differences

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

--- reachable_pushdown_configurations_are_regular [2007/05/30 23:23]
vkuncak
+++ reachable_pushdown_configurations_are_regular [2007/05/30 23:33]
vkuncak
@@ Line 19: / Line 19: @@
 === Multi-automata ===
-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.
+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.