Mercurial > 13ss.theoinf
changeset 30:4e28756e3dba
allow epsilon-edges in PDAs
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Mon, 10 Jun 2013 23:54:54 +0200 |
| parents | 19b94914c0db |
| children | 90ffda7e20c7 |
| files | notes/tex/ue07_notes.tex notes/ue07_notes.pdf |
| diffstat | 2 files changed, 4 insertions(+), 3 deletions(-) [+] |
line wrap: on
line diff
--- a/notes/tex/ue07_notes.tex Mon Jun 10 23:39:36 2013 +0200 +++ b/notes/tex/ue07_notes.tex Mon Jun 10 23:54:54 2013 +0200 @@ -97,7 +97,7 @@ \item endlichen Menge von \alert{Zuständen} $Q$ \item endlichen \alert{Eingabealphabet} $\Sigma$ \item endlichen \alert{Kelleralphabet} $\Gamma$ - \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$ \item \alert{Startzustand} $q_0 \in Q$ \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$ \item Menge von \alert{Endzuständen} $F \subseteq Q$ @@ -121,7 +121,7 @@ \begin{definition}[Kellerautomat] Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem \begin{itemize} - \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$ \end{itemize} \end{definition} @@ -142,7 +142,8 @@ \begin{definition}[Kellerautomat] Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem \begin{itemize} - \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ + + \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$ \end{itemize} \end{definition}