Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
sav07_lecture_20 [2007/06/05 11:02] kremena.diatchka |
sav07_lecture_20 [2007/06/05 11:19] kremena.diatchka |
||
|---|---|---|---|
| Line 163: | Line 163: | ||
| modifies: FileState | modifies: FileState | ||
| ensures: FileState = open | ensures: FileState = open | ||
| + | |||
| + | |||
| Line 210: | Line 212: | ||
| === Convergence of automata for reachable configurations === | === Convergence of automata for reachable configurations === | ||
| - | One of the main results of this paper is an algorithm which, given a set of states S, computes the set of all predecessors of S, denoted by $pre^{*}(S)$. The states in $pre^{*}(S)$ are regular, i.e. they can be represented using a finite state automaton. | + | One of the main results of this paper is an algorithm which, given a set of states $S$, computes the set of all predecessors of $S$, denoted by $pre^{*}(S)$. The states in $pre^{*}(S)$ are regular, i.e. they can be represented using a finite state automaton. |
| In the paper, a pushdown system is defined as a triplet $\mathcal{P} = (P, \Gamma, \Delta)$ where | In the paper, a pushdown system is defined as a triplet $\mathcal{P} = (P, \Gamma, \Delta)$ where | ||
| Line 239: | Line 241: | ||
| * if $q \stackrel{\w}{\longrightarrow} q''$ and $q'' \stackrel{\gamma}{\longrightarrow} q'$ then $q \stackrel{w\gamma}{\longrightarrow} q'$ | * if $q \stackrel{\w}{\longrightarrow} q''$ and $q'' \stackrel{\gamma}{\longrightarrow} q'$ then $q \stackrel{w\gamma}{\longrightarrow} q'$ | ||
| - | $\mathcal{A}$ accepts or recognizes a configuration $\langle p^{i},w \rangle$ if $s^{i} \stackrel{w}{\longrightarrow} q$ for some $q \in F$. The set of configurations recognized by $\mathcal{A}$ is denoted $Conf($\mathcal{A}$)$. As stated before, a set of configurations is regular if it recognized by some MA. | + | $\mathcal{A}$ accepts or recognizes a configuration $\langle p^{i},w \rangle$ if $s^{i} \stackrel{w}{\longrightarrow} q$ for some $q \in F$. The set of configurations recognized by $\mathcal{A}$ is denoted $Conf(\mathcal{A})$. As stated before, a set of configurations is regular if it recognized by some MA. |
| + | |||
| + | Section 2.2 of the paper explains how, given a regular set of configurations $C$ of a PDS $\mathcal{P}$ recognized by an MA $\mathcal{A}$, we can construct another MA $\mathcal{A}_{pre*}$ recognizing $pre^{*}(C)$ (refer to paper for details). | ||
| + | So the idea in the end is to make $C$ include those undesirable (error) states, and then check whether $pre^{*}(C)$ includes the starting state configurations (in other words, whether any of the error states are reachable from the start state). | ||
| ==== References ==== | ==== References ==== | ||