Mercurial > 13ss.theoinf

comparison notes/tex/ue07_notes.tex @ 30:4e28756e3dba

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
29:19b94914c0db 30:4e28756e3dba
95 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem 95 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
96 \begin{itemize} 96 \begin{itemize}
97 \item endlichen Menge von \alert{Zuständen} $Q$ 97 \item endlichen Menge von \alert{Zuständen} $Q$
98 \item endlichen \alert{Eingabealphabet} $\Sigma$ 98 \item endlichen \alert{Eingabealphabet} $\Sigma$
99 \item endlichen \alert{Kelleralphabet} $\Gamma$ 99 \item endlichen \alert{Kelleralphabet} $\Gamma$
100 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ 100 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$
101 \item \alert{Startzustand} $q_0 \in Q$ 101 \item \alert{Startzustand} $q_0 \in Q$
102 \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$ 102 \item \alert{Kellerinitialisierung} $Z_0 \in \Gamma$
103 \item Menge von \alert{Endzuständen} $F \subseteq Q$ 103 \item Menge von \alert{Endzuständen} $F \subseteq Q$
104 \end{itemize} 104 \end{itemize}
105 \end{definition} 105 \end{definition}
119 \setbeamercovered{dynamic} 119 \setbeamercovered{dynamic}
120 120
121 \begin{definition}[Kellerautomat] 121 \begin{definition}[Kellerautomat]
122 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem 122 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
123 \begin{itemize} 123 \begin{itemize}
124 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ 124 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$
125 \end{itemize} 125 \end{itemize}
126 \end{definition} 126 \end{definition}
127 127
128 \vfill 128 \vfill
129 129
140 \setbeamercovered{dynamic} 140 \setbeamercovered{dynamic}
141 141
142 \begin{definition}[Kellerautomat] 142 \begin{definition}[Kellerautomat]
143 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem 143 Ein \alert{PDA} (Push-Down-Automaton) ist ein Tupel $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ aus einer/einem
144 \begin{itemize} 144 \begin{itemize}
145 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \times \Gamma \mapsto P(Q \times \Gamma^*)$ 145
146 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \times \Gamma \mapsto P(Q \times \Gamma^*)$
146 \end{itemize} 147 \end{itemize}
147 \end{definition} 148 \end{definition}
148 149
149 \vfill 150 \vfill
150 151