3. Vorlesung

Es wurden die folgenden Definitionen eingeführt

• Deterministisch endlicher Automat (DEA)
• Fortsetzung

Satz: Potenzmengenkonstruktion

Zu jedem NEA kann man einen äquivalenten DEA konstruieren.

Idee:

Neue Folge ausgehend von {\(q_o\)} längs aller Folgen von Buchstaben die Mengen von Zuständen, die so erreichbar sind.

Formal:

Sei \(a = (Q, \varSigma, q_0, \Delta, F)\) gegeben, so definiere \(a' = (Q', \varSigma, q_0', \delta', F')\), so gilt:

\[\begin{split}&Q' = 2^Q = \{ R \mid E \subseteq Q \} \text{ Potenzmenge von Q} \\ &q_0' = \{ q_0 \} \\ &\text{Für } R \subset Q: \\ &\delta'(R, a) = \{ \underline{q} \mid \exists r \in R, (r,a,\underline{q}) \in \Delta \} \\ &F' = \{ R \mid R \subseteq Q, R \cap F \neq Q \}\end{split}\]

Behauptung: \(a: p \rightarrow^w q \Longleftrightarrow q \in \delta'(\{ p \}, w)\)

Beweis: Per Induktion über (w)

\(\underline{IA:}\) Sei \(\mid w \mid = 0\) und \(a: p \rightarrow^{\varepsilon} q \Longleftrightarrow p = q \Longleftrightarrow q \in \delta'(\{p\}, \varepsilon)\).

\(\underline{IS:}\) Sei \(w = v a\) und es gelte als IV \(a: p \rightarrow^v r \Longleftrightarrow r \in \delta'(\{ p \}, v)\), so gilt:

\[\begin{split}a: p \rightarrow^{va} q &\Longleftrightarrow \exists r \in Q: a: p \rightarrow^v r \\ &\Longleftrightarrow \exists r \in Q: r \in \delta'(\{ p \}, v)\end{split}\]

Damit gilt:

\[\begin{split}a: p \rightarrow^{va} q &\Longleftrightarrow \exists r \in Q: a: p \rightarrow^v r, a: r \rightarrow^a q \\ &\Longleftrightarrow^{IV} \exists r \in Q: r \in \delta'(\{ p \}, v), (r,a,q) \in \Delta \\ &\Longleftrightarrow^{Def. \delta'} q \in \delta'(R, a) = \delta'(\delta'(\{ p \}, v), a) \\ &\Longleftrightarrow^{Fortsetzung \delta' auf \varSigma^*} q \in \delta'(\{ p \}, va)\end{split}\]

Für die Akzeptanz gilt also

\[\begin{split}\text{a akzeptiert w} &\Longleftrightarrow \exists q \in F: a: q_0 \rightarrow^w q \\ &\Longleftrightarrow^{Behauptung} \exists q \in F: q \in \delta'(\{ q_0 \}, w) \\ &\Longleftrightarrow \delta'(\{ q_0 \}, w) \cap F \neq \emptyset \\ &\Longleftrightarrow^{Def. F'} \delta'(\{ q_0 \}, w) \in F' \\ &\Longleftrightarrow^{Def. F'} \text{a' akzeptiert w}\end{split}\]

Das bedeutet a und a’ sind äquivalent (L(a) = L(a’)).

Es wurden die folgenden Definitionen eingeführt

• Regulär
• Beschränkung auf erreichbare Zuständen

Identifizierung äquivalenter Zustände

Definition

Zwei Zustände q, q’ eines DEA \(a = (Q, \varSigma, q_0, \delta, F)\) heißen äquivalent, falls \(\forall w \in \varSigma^*: (\delta(q,w) \in F \Longleftrightarrow \delta(q', w) \in F)\)

Schreibweise

\(q \sim q'\)

Bemerkungen

1. \(\sim\) ist eine Äquivalenzrelation. Es sei \(\overline{q}\) die Äquivalenzklasse von q (\(\overline{q} = \{ p \mid p \sim q \}\))

2. \(q \sim q', a \in \varSigma \Rightarrow \delta(q,a) \sim \delta(q', a)\)

   Ansonsten:

   \[\begin{split}\exists w \in \varSigma^*: &[\delta(\delta(q,a),w) \in F \wedge \delta(\delta'(q', a), w) \notin F \\ &\text{oder } \delta(\delta(q,a),w) \notin F \wedge \delta(\delta'(q', a), w) \in F] \\ &\Longrightarrow \exists w \in \varSigma^*: &[\delta(q,aw) \in F \wedge \delta'(q', aw) \notin F \\ &\text{oder } \delta(q,aw) \notin F \wedge \delta(q', aw) \in F] \\ &\Longrightarrow q \nsim q' \Longrightarrow WSP.\end{split}\]

Es wurden die folgenden Definitionen eingeführt

• Äquivalenzklassen
• Reduzierter DEA