Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav07_lecture_20 [2007/06/05 09:44] kremena.diatchka |
sav07_lecture_20 [2007/06/05 11:02] kremena.diatchka |
||
|---|---|---|---|
| Line 226: | Line 226: | ||
| == Multi-automata == | == Multi-automata == | ||
| - | A multi-automaton for a PDS $\mathcal{P}$ (MA for short) is a tuple $\mathcal{A} = (\Gamma, Q, \delta, I, F)$ where | + | Let $\mathcal{P} = (P, \Gamma, \Delta)$ be a PDS with $P=\{p^{1},...,p^{m}\}$. A multi-automaton (MA for short) for $\mathcal{P}$ is a tuple $\mathcal{A} = (\Gamma, Q, \delta, I, F)$ where |
| $Q$ is a finite set of states | $Q$ is a finite set of states | ||
| Line 239: | Line 239: | ||
| * 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. | ||