eindige-automaten.tex

\documentclass[main.tex]{subfiles}
\begin{document}

\chapter{Eindige automaten}
\label{cha:eindige-automaten}

\section{Niet-deterministische eindige toestandsautomaten}
\label{sec:niet-deterministische-eindige-automaten}

\begin{de}
  Een \term{niet-deterministische eindige toestandsautomaat} (\term{NFA}) is een 5-tal $(Q,\Sigma,\delta,q_{s},F)$.
  \begin{itemize}
  \item $Q$ is een eindige verzameling toestanden.
  \item $\Sigma$ is een alfabet.
  \item $\delta$ is de overgangsfunctie van de automaat.
  \[ \delta: Q \times \Sigma_{\epsilon} \rightarrow \mathcal{P}(Q) \]
  \item $q_{s} \in Q$ is de starttoestand.
  \item $F \subseteq Q$ is de verzameling aanvaardbare eindtoestanden.
  \end{itemize}
\end{de}

\begin{de}
  De verzameling van alle NFA's wordt genoteerd als $NFA$.
  De verzameling van alle NFA's over een alfabet $\Sigma$ wordt genoteerd als $NFA_{\Sigma}$.
\end{de}

\begin{de}
  Een \term{string} $s$ wordt \term{aanvaard door een NFA} $N=(Q,\Sigma,\delta,q_{s},F)$ als $s$ geschreven kan worden als een opeenvolging $a_{1}a_{2}\ldots a_{n}$ met $a_{i} \in \Sigma_{\epsilon}$ en een opeenvolging toestanden $t_{1}t_{2}\ldots t_{n+1}$ zodat:
  \begin{itemize}
  \item $t_{1} = q_{s}$
  \item $t_{i+1} \in \delta(t_{i},a_{i})$
  \item $t_{n+1} \in F$
  \end{itemize}
  Merk op dat we tussen elke twee symbolen een willekeurig aantal keer $\epsilon$ kunnen zetten.
\end{de}

\begin{de}
  De \term{taal} $L_{N}$ \term{bepaald door een NFA} $N$ bevat alle strings die $N$ aanvaardt, \textit{en geen andere strings}.
\end{de}

\begin{de}
  Twee \term{equivalente NFA's} $N_{1}$ en $N_{2}$ bepalen dezelfde taal.
  \[ n_{1} \sim n_{2} \Leftrightarrow L_{N_{1}} = L_{N_{2}} \]
\end{de}

\begin{st}
  \label{st:equivalentierelatie-NFA}
  Het concept van `equivalentie' van NFA's vormt een equivalentierelatie op de verzameling van alle NFA's.

  \begin{proof}
    Inderdaad, de gelijkheid \textit{van talen} vormt een equivalentierelatie.
  \end{proof}
\end{st}

\begin{opm}
  Met elke equivalentieklasse van NFA's ten opzichte van de equivalentie van NFA's komt dus precies \'e\'en taal overeen.
\end{opm}

\begin{st}
  \label{st:hoogstens-een-eindtoestand-NFA}
  Voor elke NFA bestaat er een equivalente NFA met hoogstens \'e\'en aanvaardbare eindtoestand.

  \begin{proof}
    Kies een willekeurige NFA $n$.
    We onderscheiden nu drie gevallen op basis van het aantal aanvaardbare eindtoestanden $|F|$ in $n$.
    \begin{enumerate}
    \item $|F| = 0 \vee |F| = 1$\\
      Wanneer $n$ hoogstens \'e\'en aanvaardbare eindtoestand bevat, is de NFA equivalent met een NFA met hoogstens \'e\'en aanvaardbare eindtoestand, namelijk zichzelf.\eiref{st:equivalentierelatie-NFA}.
    \item $|F| > 1$\\
      Wanneer $n$ meer dan \'e\'en aanvaardbare toestand bevat, kunnen we een equivalente NFA $n'$ construeren met precies \'e\'en aanvaardbare eindtoestand.
      Kies willekeurig een aanvaardbare eindtoestand en noem deze $f$. 
      Voeg nu een $\epsilon$ boog toe van elke andere eindtoestand naar $f$.
      Verander tenslotte de andere aanvaardbare eindtoestanden in onaanvaardbare eindtoestanden om de NFA $n'$ te bekomen.
    \end{enumerate}
  \end{proof}
\end{st}

\begin{st}
  Voor elke NFA bestaat er een equivalente NFA waar je nooit in vast komt te zitten.

  \begin{proof}
    Kies een willekeurige NFA $n$.
    We construeren nu een equivalente NFA $n'$ waarin je nooit vast kan komen te zitten.
    Creer een nieuwe onaanvaardbare staat $d$. Ga nu voor elke staat van $n$ na voor welke symbolen er een boog ontbreekt.
    Maak in elk van die staten een boog van die staat naar $d$ voor elk van die symbolen.
    Voeg bovendien voor elk symbool in het alfabet een boog van $d$ naar zichzelf toe met dat symbool.
    De overgangsfunctie $\delta$ van $n$ is nu een totale functie, dus in $n'$ kom je nooit vast te zitten.
  \end{proof}
\end{st}

\begin{de}
  Een \term{transititabel} is een tabel die de funtie $\delta$ voorstelt voor een automaat.
  De tabel heeft drie kolommen. Elke rij vormt een deel van de werking van $\delta$.
  In de eerste kolom staat een staat, in de tweede een symbool, en in de derde een verzameling van staten.                   
\end{de}

\subsection{De algebra van NFA's}
Vanaf deze sectie gaan we ervan uit dat een NFA hoogstens \'e\'en aanvaardbare eindtoestand heeft waaruit bovendien geen pijlen vertrekken, zonder verlies van algemeenheid.\eiref{st:hoogstens-een-eindtoestand-NFA}
\label{sec:de-algebra-van-nfas}

\begin{de}
  De \term{unie} $n_{1} \cup n_{2}$ van twee NFA's $n_{1}$ en $n_{2}$ is de NFA $n$ die de unie van de talen $L_{n_{1}}$ en $L_{n_{2}}$ aanvaardt.
\end{de}

\begin{st}
  \label{st:unie-nfas}
  Constructie van de \term{unie van NFA's}\\
  Het is steeds mogelijk om de unie van twee NFA's te construeren.

  \begin{proof}
    Zij $n_{1} = (Q_{1},\Sigma,\delta_{1},q_{s1},\{q_{f1}\})$ en $n_{2} = (Q_{2},\Sigma,\delta_{2},q_{s2},\{q_{f2}\})$ twee willekeurige NFA's. We construeren nu de unie $n = n_{1} \cup n_{2} = (O,\Sigma,\delta,q,\{q_{f}\})$ van deze NFA's.
    De informele constructie ziet u in figuur \ref{fig:nfa_unie}.
    \begin{figure}[H]
      \centering
      \includegraphics[width=0.5\textwidth]{assets/nfa_unie.png}      
      \caption{De unie van twee NFA's}
      \label{fig:nfa_unie}
    \end{figure}
    Formeel beschrijven we $n$ als volgt.
    \begin{itemize}
    \item $Q = Q_{1} \cup Q_{2} \cup \{ q_{s}, q_{f} \}$ waarbij $q_{s}$ en $q_{f}$ nieuwe toestanden zijn.
    \item $F = {q_{f}}$
    \item $\delta$ wordt aangepast als volgt:
      \begin{itemize}
      \item $\forall q \in Q_{i}\setminus\{q_{f_{i}}\},\ \forall x \in \Sigma_{\epsilon}:\ \delta(q,x) = \delta_{i}(q,x)$
      \item $\delta(q_{s},\epsilon) = \{q_{s1},q_{s2}\}$
      \item $\forall x \in \Sigma:\ \delta(q_{s},x) = \emptyset$
      \item $\delta(q_{f1},\epsilon) = \{q_{f}\}$ en $\delta(q_{f2},\epsilon) = \{q_{f}\}$
      \item $\forall x \in \Sigma:\ \delta(q_{f1},x) = \emptyset$, $\delta(q_{f2},x) = \emptyset$ en $\delta(q_{f},x) = \emptyset$ 
      \end{itemize}
    \end{itemize}
  \end{proof}
\end{st}

\begin{de}
  De \term{concatenatie} $n_{1}n_{2}$ van twee NFA's $n_{1}$ en $n_{2}$ is de NFA $n$ die de concatenatie van de talen $L_{n_{1}}$ en $L_{n_{2}}$ aanvaardt.
\end{de}

\begin{st}
  \label{st:concatenatie-nfas}
  Constructie van de \term{concatenatie van NFA's}\\
  Het is steeds mogelijk om de concatenatie van twee NFA's te construeren.

  \begin{proof}
    Zij $n_{1} = (Q_{1},\Sigma,\delta_{1},q_{s1},\{q_{f1}\})$ en $n_{2} = (Q_{2},\Sigma,\delta_{2},q_{s2},\{q_{f2}\})$ twee willekeurige NFA's. We construeren nu de concatenatie $n = n_{1}n_{2} = (O,\Sigma,\delta,q,\{q_{f}\})$ van deze NFA's.
    De informele constructie ziet u in figuur \ref{fig:nfa_concat}.
    \begin{figure}[H]
      \centering
      \includegraphics[width=0.7\textwidth]{assets/nfa_concat.png}      
      \caption{De concatenatie van twee NFA's}
      \label{fig:nfa_concat}
    \end{figure}
    Formeel beschrijven we $n$ als volgt.
    \begin{itemize}
    \item $Q = Q_{1} \cup Q_{2} \cup \{ q_{s}, q_{f} \}$ waarbij $q_{s}$ en $q_{f}$ nieuwe toestanden zijn.
    \item $F = {q_{f}}$
    \item $\delta$ wordt aangepast als volgt:
      \begin{itemize}
      \item $\forall q \in Q_{i}\setminus\{q_{f_{i}}\},\ \forall x \in \Sigma_{\epsilon}:\ \delta(q,x) = \delta_{i}(q,x)$
      \item $\delta(q_{s},\epsilon) = \{q_{s1}\}$
      \item $\forall x \in \Sigma:\ \delta(q_{s},x) = \emptyset$
      \item $\delta(q_{f1},\epsilon) = \{q_{s2}\}$
      \item $\delta(q_{f2},\epsilon) = \{q_{f}\}$
      \item $\forall x \in \Sigma:\ \delta(q_{f1},x) = \emptyset$, $\delta(q_{f2},x) = \emptyset$ en $\delta(q_{f},x) = \emptyset$ 
      \end{itemize}
    \end{itemize}
  \end{proof}
\end{st}

\begin{de}
  De \term{Kleene-ster} van een NFA $n'$ is de NFA $n$ die de Kleenester van de taal $L_{n'}$ aanvaardt.
\end{de}

\begin{st}
  \label{st:ster-nfa}
  Constructie van de \term{Kleene-ster van een NFA}\\
  Het is steeds mogelijk om de Kleene-ster van een NFA te construeren.

  \begin{proof}
    Zij $n' = (Q',\Sigma,\delta',q_{s},\{q_{f}'\})$ een willekeurige NFA. We construeren nu de Kleene-ster $n = (O,\Sigma,\delta,q,F)$ van deze NFA.
    De informele constructie ziet u in figuur \ref{fig:nfa_kleene}.
    \begin{figure}[H]
      \centering
      \includegraphics[width=0.5\textwidth]{assets/nfa_kleene.png}      
      \caption{De Kleenester van een NFA}
      \label{fig:nfa_kleene}
    \end{figure}
    Formeel beschrijven we $n$ als volgt.
    \begin{itemize}
    \item $Q = Q' \cup \{ q_{s}, q_{f} \}$ waarbij $q_{s}$ en $q_{f}$ nieuwe toestanden zijn.
    \item $F = {q_{f}}$
    \item $\delta$ wordt aangepast als volgt:
      \begin{itemize}
      \item $\forall q \in Q'\setminus\{q_{f}'\},\ \forall x \in \Sigma_{\epsilon}:\ \delta(q,x) = \delta_{i}(q,x)$
      \item $\delta(q_{s},\epsilon) = \{q_{s}'\}$
      \item $\forall x \in \Sigma:\ \delta(q_{s},x) = \emptyset$
      \item $\delta(q_{f}',\epsilon) = \{q_{f}\}$
      \item $\delta(q_{f},\epsilon) = \{q_{s}\}$
      \item $\delta(q_{s},\epsilon) = \{q_{f}\}$
      \item $\forall x \in \Sigma:\ \delta(q_{f}',x) = \emptyset$ en $\delta(q_{f},x) = \emptyset$
      \end{itemize}
    \end{itemize}
  \end{proof}
\end{st}

\begin{de}
  Het \term{complement} van een NFA $n$ is de NFA $n^{c}$ die het complement $L_{n}^{c}$ van de taal $L_{n}$ aanvaardt.
\end{de}

\begin{st}
  \label{st:complement-nfa}
  Constructie van het \term{complement van een NFA}\\
  Het is steeds mogelijk om het complement van een NFA te construeren.

  \begin{proof}
    Zij $n' = (Q',\Sigma,\delta,q_{s},F)$ een willekeurige NFA. We construeren nu het complement $n = (O,\Sigma,\delta,q_{s},F)$ van deze NFA.
    De informele constructie ziet u in figuur \ref{fig:nfa_kleene}.
    \begin{figure}[H]
      \centering
      \includegraphics[width=0.5\textwidth]{assets/nfa_complement.png}      
      \caption{Het complement van een NFA}
      \label{fig:nfa_complement}
    \end{figure}
    Formeel beschrijven we $n$ als volgt.
    \begin{itemize}
    \item $Q = Q'$.
    \item $F = Q'\setminus F'$.
    \end{itemize}
  \end{proof}
\end{st}

\begin{ei}
  NFA's, uitgerust met de unie, de doorsnede, het complement en de concatenatie vormen een algebra.
  \begin{proof}
    Inderdaad, zowel de unie\stref{st:unie-nfas}, de doorsnede, het complement\stref{st:complement-nfa} als de concatenatie\stref{st:concatenatie-nfas} zijn inwendig.
  \end{proof}
\end{ei}

\subsection{Van reguliere expressie naar NFA}
\label{sec:van-reguliere-expressie-naar-nfa}

\begin{de}
  Definieer de NFA $NFA_{\epsilon}$ als $(Q, \Sigma, \delta, q_{s}, F)$.

  \begin{itemize}
  \item $Q = \{q_{s},q_{d}\}$.
  \item 
    \[ \forall q \in Q, c \in \Sigma:\ \delta(q,c) = q_{d} \]
  \item $F = \{q_{s}\}$
  \end{itemize}

  \begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{assets/nfa_epsilon.png}      
    \caption{De NFA $NFA_{\epsilon}$}
    \label{fig:nfa_epsilon}
  \end{figure}
\end{de}

\begin{ei}
  \label{ei:nfa-epsilon}
  De NFA $NFA_{\epsilon}$ bepaalt de taal $\{ \epsilon \}$.

  \begin{proof}
    Aangezien de starttoestand van $NFA_{\epsilon}$ aanvaardbaar is accepteert $NFA_{\epsilon}$ zeker $\epsilon$.
    Elke string van meer dan $0$ symbolen wordt bovendien verworpen, want dan eindigt de NFA in toestand $q_{d}$.
  \end{proof}
\end{ei}

\begin{de}
  Definieer de NFA $NFA_{\phi}$ als $(Q, \Sigma, \delta, q_{s}, \emptyset)$.

  \begin{itemize}
  \item $Q = \{q_{s}\}$
  \item 
    \[ \forall c \in \Sigma:\ \delta(q,c) = q_{s} \]
  \end{itemize}

  \begin{figure}[H]
    \centering
    \includegraphics[width=0.2\textwidth]{assets/nfa_phi.png}      
    \caption{De NFA $NFA_{\phi}$}
    \label{fig:nfa_phi}
  \end{figure}
\end{de}

\begin{ei}
  \label{ei:nfa-phi}
  De NFA $NFA_{\phi}$ bepaalt de lege taal $\emptyset$.

  \begin{proof}
    Er zijn geen aanvaarbare toestanden in $NFA_{\phi}$, dus $NFA_{\phi}$ kan geen enkele string aanvaarden.
  \end{proof}
\end{ei}

\begin{de}
  Definieer de NFA $NFA_{a}$ (met $a$ in $\Sigma$) als $(Q, \Sigma, \delta, q_{s}, F)$.

  \begin{itemize}
  \item $Q = \{q_{s},q_{f},q_{d}\}$
  \item $\delta$
    \[ \delta(q_{s}, a) = q_{f} \]
    \[ \forall c \in \Sigma\setminus\{a\}:\ \delta(q_{s}, c) = q_{d} \]
    \[ \forall c \in \Sigma:\ \delta(q_{f}, c) = q_{d}\]
    \[ \forall c \in \Sigma:\ \delta(q_{d}, c) = q_{d}\]
  \item $F = \{q_{f}\}$
  \end{itemize}

  \begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{assets/nfa_a.png}      
    \caption{De NFA $NFA_{a}$}
    \label{fig:nfa_a}
  \end{figure}
\end{de}

\begin{ei}
  \label{ei:nfa-a}
  Voor elk symbool $a$ van het alfabet $\Sigma$ bepaalt de NFA $NFA_{a}$ de taal $\{ a \}$.

  \begin{proof}
    $NFA_{a}$ aanvaardt de lege string niet omdat de starttoestand niet aanvaardbaar is.
    $NFA_{a}$ zal in $q_{f}$ belanden voor de string $a$, en voor elke andere string in $q_{d}$.
    $NFA_{a}$ bepaalt dus de taal $\{ a \}$.
  \end{proof}
\end{ei}

\begin{de}
  Definieer nu \term{NFA van een reguliere expressie}, samen met de vorige definitie als volgt:
  \[
  \begin{array}{r|ll}
    E & NFA_{E}\\
    \hline
    \epsilon & NFA_{\epsilon}\\
    \phi & NFA_{\phi}\\
    E_{1}E_{2} & NFA_{E_{1}E_{2}} &= NFA_{E_{1}}NFA_{E_{2}}\\
    E_{1}|E_{2} & NFA_{(E_{1}|E_{2})} &= NFA_{E_{1}} \cup NFA_{E_{2}}\\
    E^{*} & NFA_{E^{*}} &= NFA_{E}^{*}\\
  \end{array}
  \]
\end{de}

\begin{st}
  \label{st:regex-naar-NFA}
  Voor elke reguliere expressie bestaat er een NFA die dezelfde taal bepaalt.

  \begin{proof}
    De NFA van een reguliere expressie bepaalt dezelfde taal als de reguliere expressie. \eiref{ei:nfa-epsilon} \eiref{ei:nfa-phi} \eiref{ei:nfa-a} \stref{st:unie-nfas} \stref{st:concatenatie-nfas} \stref{st:ster-nfa} 
  \end{proof}
\end{st}

\subsection{NFA naar reguliere expressie}
\begin{de}
  Een \term{gegeneraliseerde niet-deterministische eindige toestandsautomaat} (\term{GNFA}) is een 5-tal $(Q,\Sigma,\delta,q_{s},q_{f}$).
  \begin{itemize}
  \item $Q$ is een eindige verzameling toestanden.
  \item $\Sigma$ is een alfabet.
  \item $\delta$ is de overgangsfunctie.
  Merk op dat deze functie twee staten als argument neemt in plaats van een staat en een symbool.
    \[
    \delta: Q\setminus\{q_{s}\} \times Q\setminus\{q_{f}\} \rightarrow RegEx_{\Sigma}
    \]
  \item $q_{s}$ is de starttoestand.
  \item $q_{f}$ is de aanvaardbare eindtoestand.
  \end{itemize}
\end{de}
\begin{opm}
  Een GNFA heeft de volgende (informele) eigenschappen.
  \begin{itemize}
  \item Er is precies \'e\'en eindtoestand en die is verschillend van de starttoestand.
  \item Er is precies \'e\'en boog van elke toestand naar de eindtoestand
  \item Uit de eindtoestand vertrekken geen pijlen.
  \item Tussen elke twee toestanden (behalve de begin- en eindtoestand) vertrekt precies \'e\'en boog in beide richtingen
  \item Er is precies \'e\'en boog van elke toestand (behalve de begin- en eindtoestand) naar zichzelf.
  \item De bogen hebben een reguliere expressie als label.
  \end{itemize}
\end{opm} 

\begin{de}
  Een string $s$ wordt aanvaard door een GNFA als er een opeenvolging reguliere expressies $E_{1},E_{2},\dotsc,E_{n}$ bestaat zodat $s$ wordt aanvaard door de concatenatie van die opeenvolging reguliere expressies en zodat die reguliere expressies een pad $t_{1},t_{2},\dotsc,t_{n+1}$ vormen in de GNFA. 
  \begin{itemize}
  \item $t_{1} = q_{s}$
  \item $\delta(t_{i},t_{i+1}) = E_{i}$
  \item $t_{n+1} = q_{f}$
  \end{itemize}
\end{de}

\begin{st}
  \label{st:nfa-naar-regex}
  We kunnen iedere NFA omzetten in een reguliere expressie die dezelfde taal bepaalt.
  
  \begin{proof}
    We zetten constructief een willekeurige NFA $n$ om naar een GNFA $g$.
    \begin{enumerate}
    \item Maak van de NFA een GNFA:\\
      Voer een nieuwe begintoestand, en een nieuwe unieke eindtoestand.
      Teken een $\epsilon$-boog van de nieuwe begintoestand naar de oude, alsook een $\epsilon$-boog van de oude eindtoestand naar de nieuwe.
      Teken alle ontbrekende bogen met een $\phi$ (deze mogen toch niet gevolgd worden).
      Het is evident dat deze GNFA dezelfde taal bepaalt als de originele NFA.
    \item Reduceer de GNFA:\\
      Kies een willekeurige toestand $X$ verschillend van de begin- of eindtoestand.
      Verwijder $X$ als volgt: Kies toestanden $A$ en $B$ zodat er bogen zijn van $A$ naar $B$ met reguliere expressie $E_{4}$, van $A$ naar $X$ met $E_{1}$, van $X$ naar zichzelf met $E_{2}$ en van $X$ naar $B$ met $E_{3}$.
      \begin{figure}[H]
        \centering
        \includegraphics[width=0.3\textwidth]{assets/nfa-gnfa1.png}
        \text{\hspace{1cm}wordt\hspace{1cm}}
        \includegraphics[width=0.3\textwidth]{assets/nfa-gnfa2.png}   
        \label{fig:nfa-gnfa}
      \end{figure}
      Vervang het label op de boog van $A$ naar $B$ door $(E_{4}|E_{1}E_{2}^{*}E_{3})$.
      Doe dit voor alle koppels $A$ en $B$ ten opzichte van $X$ en verwijder tenslotte $X$.
      \[
      \forall a,b,c: ((\delta(a,b)=E_{4})\wedge (\delta(a,x)=E_{1})\wedge (\delta(x,x)=E_{2})\wedge (\delta(x,b)=E_{3})) 
      \]
      \[
      \Rightarrow \delta'(a,b)=(E_{4}|E_{1}E_{2}^{*}E_{3})
      \]
      Itereer dit proces tot enkel nog de begin- en eindtoestand overblijven.
      Dit proces verandert de bepaalde taal niet.
      Noem de machine voor het proces $GNFA_{voor}$ en na het proces $GNFA_{na}$.
      Kies nu een willekeurige string $s \in \Sigma^{*}$.
      \begin{itemize}
      \item
        Als $s$ aanvaard werd door $GNFA_{voor}$ met een pad dat $X$ niet bevat, dan wordt $s$ door datzelfde pad in $GNFA_{na}$ aanvaard.
        Als het pad $X$ wel bevat, dan zijn er toestanden $A$ en $B$ zodat $AX^{n}B$ met $n\in \mathbb{N}_{0}$ een opeenvolging is in het pad. De reguliere expressie op de bogen $AX$, $XX$, $XB$ zijn $E_{1}$, $E_{2}$ en $E_{3}$. Bijgevolg kost van $A$ naar $B$ gaan langs $X$ een stukje string dat voldoet aan $E_{1}E_{2}^{*}E_{3}$. Die reguliere expressie staat in $GNFA_{na}$ in de boog $AB$, dus $s$ wordt ook aanvaard door $GNFA_{na}$.
      \item
        Als $s$ aanvaard wordt door $GNFA_{na}$ dan bevat het acceptatiepad alleen maar toestanden verschillend van $X$. Op een boog van $A$ naar $B$ staat de reguliere expressie $E_{4}|E_{1}E_{2}^{*}E_{3}$. Die reguliere expressie gebruiken kost een stukje string dat voldoet aan $E_{4}$ of $E_{1}E_{2}^{*}E_{3}$. In $GNFA_{voor}$ komt dat overeen met ofwel boog $AB$ volgen, ofwel $AX$, gevolgd door $n$ keer $XX$ en $XB$. Dit houdt in dat de string ofwel het pad langs $X$ nodig had, ofwel het pad zonder $X$, langs $A$ en $B$. In beide gevallen aanvaardt $GNFA_{voor}$ ook $s$.
      \end{itemize}
    \item Bepaal de reguliere expressie.\\
      De overblijvende GNFA heeft nu precies twee toestanden met \'e\'e boog daartussen.
      De reguliere expressie $E$ van die boog is precies de reguliere expressie die we zochten.
    \end{enumerate}
  \end{proof}
\end{st}

\begin{gev}
  \label{gev:reguliere-taal-NFA}
  Elke reguliere taal wordt bepaald door een NFA.
  
  \begin{proof}
    Elke reguliere taal wordt bepaald door een reguliere expressie.\eiref{ei:reguliere-taal-expressie}
    Elke reguliere expressie kan bovendien omgezet worden in een NFA die dezelfde taal bepaalt.\stref{st:nfa-naar-regex}
  \end{proof}
\end{gev}

\begin{ei}
  Er bestaat een isomorfisme tussen de algebra van NFA's en de algebra van Reguliere expressies.

  \begin{proof}
    Beschouw de vier bewerkingen in de algebra van reguliere expressies: unie $\cup_{R}$, concatenatie $\cdot_{R}$, complement $^{c}_{R}$ en doorsnede $\cap_{R}$.
    Er bestaan overeenkomstige bewerkingen in de algebra van NFA's: unie $\cup_{N}$, concatenatie $\cdot_{N}$, complement $^{c}_{R}$ en doorsnede $\cap_{N}$.
    Bovendien bestaat er een functie die een willekeurige NFA afbeeldt op een reguliere expressie die dezelfde taal bepaalt en omgekeerd.\stref{st:nfa-naar-regex} \stref{st:regex-naar-NFA}
    Er bestaat dus een eenvoudig isomorfisme tussen deze twee algebra's.
  \end{proof}
\end{ei}

\section{Deterministische eindige toestandsautomaten}
\begin{de}
  Een \term{deterministische eindige toestandsautomaat} (\term{DFA}) is een 5-tal $(Q,\Sigma,\delta,q_{s},F)$
  \begin{itemize}
  \item $Q$ is een eindige verzameling toestanden.
  \item $\Sigma$ is een alfabet.
  \item $\delta$ is de parti\"ele overgangsfunctie van de automaat.
  \[ \delta: Q \times \Sigma \rightarrow Q \]
  \item $q_{s} \in Q$ is de starttoestand.
  \item $F \subseteq Q$ is de verzameling aanvaardbare eindtoestanden.
  \end{itemize}
\end{de}

\begin{de}
  De verzameling van alle DFA's wordt genoteerd als $DFA$.
  De verzameling van alle DFA's over een alfabet $\Sigma$ wordt genoteerd als $DFA_{\Sigma}$.
\end{de}

\begin{de}
  We kunnen $\delta(q,a)$ afkorten als $q_{a}$ wanneer de $\delta$ die bedoeld wordt duidelijk is.  
\end{de}

\begin{de}
  Een string $s$ wordt aanvaard door een DFA $D$ als er een opeenvolging van symbolen $s_{1}s_{2}\dotsc s_{n}$ en een opeenvolging staten van $D$ $t_{1},t_{2},\dotsc,t_{n}$ bestaat zodat het volgende geldt.
  \begin{itemize}
  \item $t_{1} = q_{s}$
  \item $\delta(t_{i},s_{i}) = t_{i+1}$
  \item $t_{n+1} \in F$
  \end{itemize}
\end{de}

\begin{de}
  De \term{taal} $L_{D}$ \term{bepaald door een DFA} $D$ bevat alle strings die $D$ aanvaardt, \textit{en geen andere strings}.
\end{de}

\begin{de}
  Twee DFA's $d_{1}$ en $d_{2}$ zijn equivalent als ze dezelfde taal bepalen.
  \[ d_{1} \sim d_{2} \Leftrightarrow L_{D_{1}} = L_{D_{2}} \]
\end{de}

\begin{st}
  \label{st:nfa-naar-dfa}
  Elke NFA kan omgezet worden in een DFA die dezelfde taal bepaalt.
  
  \begin{proof}
    Zij $N$ een willekeurige NFA.
    \[ N = (Q_{n},\Sigma,\delta_{n},q_{n},F_{n}) \]
    We construeren nu een DFA $D$ die dezelfde taal bepaalt.
    \[ D = (Q_{d},\Sigma,\delta_{d},q_{d},F_{d}) \]
    De toestanden $Q_{d}$ voor de DFA zullen elk overeen komen met een verzameling toestanden uit de NFA.
    \[ Q_d \subseteq \mathcal{P}(Q_{n})\]
    Een eindtoestand in de DFA komt steeds overeen met een verzameling die een eindtoestand van de NFA bevat.
    \[ \forall q\in Q_{d}:\ q\in F_{d}\ \Rightarrow \exists q' \in F_{n}: q' \in q\]
    Nu rest er ons nog $\delta_{d}$ te construeren.
    \[
    \delta_{d}:\ (\mathcal{P}(Q_{n}) \times \Sigma) \rightarrow \mathcal{P}(Q_{n})
    \]
    We voeren een een afbeelding $eb$ in die elke staat in $Q_{n}$ afbeeldt op al haar epsilon bereikbare toestanden in $Q_{n}$.
    \[ eb: Q_{n} \rightarrow \mathcal{P}(Q_{n}) \]
    \begin{itemize}
    \item $eb(q)$ is de verzameling toestanden die met een aantal $\epsilon$-bogen bereikbaar is vanuit $q$.
      \[ eb(q) = \left\{ q'\ |\ (\delta(q,\epsilon) = q' \vee (\exists q'':\ \delta(q'',\epsilon) = q' \wedge q'' \in eb(q) )) \right\} \]
    \item $eb(Q)$ defineren we als volgt:
      \[ ex(Q) = \bigcup_{q\in Q} eb(q)\]
    \item $\delta_{n}(Q)$ definieren we als volgt:
      \[ \delta_{n}(Q) = \bigcup_{q\in Q} \delta(q,a) \]
    \end{itemize}
    We construeren nu $\delta_{d}$:
    \[ \forall Q\in Q_{d}:\ \delta_{d}(Q,a) = eb(\delta_{n}(Q,a)) \]
    In woorden teken een boog in de DFA van elke verzameling toestanden naar de verzameling toestanden die epsilon-bereikbaar zijn vanuit die verzameling.
    Tenslotte definieren we nog de begintoestand van $D$.
    \[ q_{sd} = eb(q_{sn}) \]
  \end{proof}
\end{st}

\begin{st}
  \label{gev:reguliere-taal-DFA}
  Elke reguliere taal wordt bepaald door een DFA
  
  \begin{proof}
    Elke reguliere taal wordt bepaald door een NFA\gevref{gev:reguliere-taal-NFA}.
    Bovendien kan elk NFA omgezet worden in een DFA die dezelfde taal bepaalt\stref{st:nfa-naar-dfa}.
  \end{proof}
\end{st}

\begin{de}
  Voor elke DFA $(Q,\Sigma,\delta,q_{s},F)$ kunnen we $\delta:\ Q \times \Sigma$ uitbreiden naar $\delta^{*}:\ Q\times \Sigma^{*}$.
  \begin{itemize}
  \item $\delta^{*}(q,\epsilon) = q$
  \item $\exists \delta(q,a) \Rightarrow \delta^{*}(q,aw) = \delta^{*}(\delta(q,a),w)$
  \end{itemize}
\end{de}

\begin{st}
  \label{st:delta-ster-identiteit}
  Voor elke DFA $(Q,\Sigma,\delta,q_{s},F)$ met een uitgebreide $\delta$: $\delta^{*}$ geldt de volgende gelijkheid:
  \[
  \delta^{*}(q,wa) = \delta(\delta^{*}(q,w),a)
  \] 
  
  \begin{proof}
    We bewijzen dit door inductie op de lengte $n$ van $w$.
    \begin{itemize}
    \item De bewering geldt voor $n=0$ ($w$ is dan de lege string.):
      \[ \delta^{*}(q,wa) = \delta^{*}(q,\epsilon a) = \delta^{*}(q,a\epsilon) = \delta^{*}(\delta(q,a),\epsilon) = \delta(q,a) = \delta(\delta^{*}(q,\epsilon),a) \]
    \item Stel dat de bewering geldt voor een bepaalde $n=k$.
    \item Als de bewering geldt voor een bepaalde $n=k$, dan geldt ze ook voor $n=k+1$.
      Kies een $w$ van lengte $k+1$ en noem het eerste symbool van $w$ $b$.
      De rest van $w$ noemen we dan $w'$.
      \[ w = w'b \]
      Nu kunnen we de bewering rechtstreeks bewijzen voor een willekeurig symbool $a$.
      \[
      \begin{array}{rll}
        \delta^{*}(q,wa) &= \delta^{*}(q,bw'a) &\\
                         &= \delta^{*}(\delta(q,b),w'a) &\\
                         &= \delta(\delta^{*}(\delta(q,b),w'),a) &=\delta(\delta^{*}(q,w),a) 
      \end{array}
      \]
    \end{itemize} 
    Als gevolg van het principe van inductie geldt de bewering voor elke $n\in \mathbb{N}$.
  \end{proof}

\end{st}

\begin{st}
  \label{st:dfa-totale-overgangsfunctie}
  Als een DFA $(Q,\Sigma,\delta,q_{s},F)$ een overgangsfunctie heeft die niet totaal is, met andere woorden, niet voor elk symbool is er in elke staat een boog, dan hoeven we hoogstens \'e\'en staat toe te voegen om een equivalente DFA te maken met een totale overgangsfunctie.

  \begin{proof}
   Kies een willekeurige DFA $D = (Q,\Sigma,\delta,q_{s},F)$ met een niet-totale overgangsfunctie.
   Maak nu een nieuwe, onaanvaardbare staat $q_{t}$, en vervolledig de overgangsfunctie $\delta$ door een koppel $((q,a),q_{t})$ toe te voegen voor elk koppel $(q,a)$ waarvoor $\delta$ onbepaald is om $\delta'$ te bekomen.
   Voeg bovendien aan $\delta'$ ook nog voor elke symbool $s$ uit het alfabet $\Sigma$ het volgende koppel toe:
   \[ ((q_{t},s),q_{t}) \]
   Nu is de overgangsfunctie $\delta'$ totaal.
   De nieuwe DFA $D' = (Q\cup\{ q_{t} \},\Sigma,\delta',q_{s},F)$ is nu bovendien equivalent met $D$ door hoogstens \'e\'en staat toe te voegen.
  \end{proof}
\end{st}

\subsection{Minimale DFA's}
\begin{de}
  \label{de:f-gelijk}
  Twee toestanden $p$ en $q$ van een DFA $(Q,\Sigma,\delta,q_{s},F)$ zijn \term{$f$-gelijk} $p\sim q$ als het volgende geldt:
  \[
  \forall w \in \Sigma^{*}:\ \delta^{*}(p,w) \in F \Leftrightarrow \delta^{*}(q,w) \in F
  \]
  In woorden: dezelfde strings worden aanvaard vanuit beide toestanden $p$ en $q$.
\end{de}

\begin{de}
  Twee toestanden $p$ en $q$ van een DFA $(Q,\Sigma,\delta,q_{s},F)$ zijn \term{$f$-verschillend} als ze niet $f$-gelijk zijn. 
\end{de}

\begin{opm}
  $f$-gelijkheid kunnen we ook definieren voor NFA's, maar dan wordt $f$-verschillend moeilijk te definieren.
\end{opm}

\begin{ei}
  $f$-gelijkheid is een equivalentierelatie, en bepaalt dus een partitionering van een verzameling staten $Q$ van een $DFA$.

  \begin{proof}
    Inderdaad, de relatie ``A is $f$-gelijk met B'' is reflexief, transitief en symmetrisch.
  \end{proof}
\end{ei}

\begin{al}
  \label{al:dfa-minimalisatie}
  \emph{$f$-gelijke toestanden vinden.}\\
  Gegeven een DFA $(Q,\Sigma,\delta,q_{s},F)$, zoeken we de partitionering van $D$ in verzamelingen van $f$-gelijke toestanden.

  \begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{assets/dfa_minimalisatie-1.png}     
    \caption{Een niet-minimale DFA}
    \label{fig:dfa-minimalisatie-1}
  \end{figure}

  \subsubsection{Pre-init}
  \textit{
    Elke staat die niet bereikbaar is vanaf $q_s$ kunnen we zonder meer verwijderen
  }

  Ga voor elke staat $q\in Q$ na of $q$ bereikbaar is vanaf $q_{s}$, zo nee, verwijder $q$.

  \begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{assets/dfa_minimalisatie-2.png}     
    \caption{Een niet-minimale DFA zonder nutteloze staten}
    \label{fig:dfa-minimalisatie-2}
  \end{figure}

  \subsubsection{Init}
  \textit{
    Kies een toestand $p$ die geen eindtoestand is.
    $p$ is zeker $f$-verschillend van elke eindtoestand.
    Alle andere paren zijn nog onbeslist.
  }

  Beschouw de ongerichte graaf $G(Q,E)$ met de toestanden $Q$ als knopen en noem $E$ de bogen van $G$.
  De graaf heeft bovendien een label voor elke boog.
  Begin met een lege verzameling $E$.
  Voeg nu voor elk paar knopen $p$ en $q$ waarvan er precies \'e\'en een aanvaardbare toestand is een boog toe tussen $p$ en $q$.
  \[ \forall p,q:\ p \in F \oplus q \in F:\ (p,q,\epsilon) \in E \]

  \begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{assets/dfa_minimalisatie-3.png}     
    \caption{De graaf $V$ na de initialisatie van het minimalisatie algoritme.}
    \label{fig:dfa-minimalisatie-3}
  \end{figure}

  \subsubsection{Repeat}
  \textit{
    Kies een paar toestanden $p$ en $q$ dat nog onbeslist is.
    Stel dat er een symbool $a$ bestaat zodat je met dat symbool van $p$ en van $q$ gaat naar twee $f$-verschillende toestanden, dan beslis je dat $p$ en $q$ $f$-verschillend zijn.
  }

  Als er twee knopen $p$ en $q$ zijn waarvoor het volgende geldt:
  \begin{itemize}
  \item Er is geen boog tussen $p$ en $q$.
    \[ \not\exists (p,q,\_) \in E \]
  \item Er bestaat een symbool zodat je met dat symbool vanuit $p$ en vanuit $q$ een toestand kan bereiken waartussen een boog is.
    \[ \exists a \in \Sigma:\ \exists(p_{a},q_{a},\_) \in V \]
  \end{itemize}
  Kies een symbool $a$ waarvoor $(p_{a},q_{a},\_)$ al een boog is van $G$ en voeg de boog $(p,q,a)$ toe.
  \[ (p,q,a) \in E \]
  Het is hier noodzakelijk om op te merken dat we de overgangsfunctie $\delta$ eigenlijk eerst totaal moeten maken.\footnote{Zie stelling \ref{st:dfa-totale-overgangsfunctie}.}

  \begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{assets/dfa_minimalisatie-4.png}     
    \caption{De graaf $V$ na alle repeat stappen van het minimalisatie algoritme.}
    \label{fig:dfa-minimalisatie-4}
  \end{figure}

  \subsubsection{Consolidate}
  \textit{
    Voor elk paar toestanden $p$ en $q$ waarvoor je nog niet beslist had, beslis je nu dat $p$ en $q$ $f$-gelijk zijn.
    Gebruik deze equivalentierelatie om $Q$ te partitioneren.
  }  

  Bouw nu de complementsgraaf $G^{c}$ van $G$.
  In $G^{c}$ is er een boog tussen elke twee knopen waartussen in $G$ geen boog was.
  Elke component van $G^{c}$ stelt nu een verzameling in de partitie van $Q$ voor in $f$-gelijke disjucnte deelverzamelingen.

  \begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{assets/dfa_minimalisatie-5.png}     
    \caption{De partitionering van Q op het einde van het minimalisatie algoritme.}
    \label{fig:dfa-minimalisatie-5}
  \end{figure}

\end{al}
\begin{st}
  Bovenstaand algoritme (\ref{al:dfa-minimalisatie}) is eindig en correct.
  \begin{proof}
    Merk op dat we niet spreken over de tijds- of ruimtecomlexiteit van dit algoritme.
    \begin{itemize}
    \item Eindigheid.\\
    Het aantal knopen in $G$ is eindig omdat de DFA een eindig aantal toestanden heeft, en het aantal is dat $\frac{N(N-1)}{2}$ met $N$ het aantal knopen van $G(Q,E)$.
    Elk van die bogen wordt bovendien een eindig aantal keer overlopen.
    \item Correctheid.\\
      We bewijzen volgende bewering voor de graaf $G$ na de ``repeat'' stap:
      \[ (p,q,\_) \in E \Leftrightarrow p \text{ en } q \text { zijn } f\text{verschillend.}\]
      \begin{itemize}
      \item \framebox{$\Rightarrow$}\\
        Als $(p,q,l)$ een boog is van $G$, dan zijn er twee mogenlijkheden.
        Ofwel is het een $\epsilon$-boog: $l=\epsilon$, ofwel is het een boog met een symbool als label: $l = a \in \Sigma$.
        Als het een $\epsilon$-boog is, dan zijn $p$ en $q$ $f$-verschillend omdat de lege string de DFA bijvoorbeeld niet in een zelfde soort toestand zou brengen.
        \[ \delta^{*}(p,\epsilon) \in F \not\Leftrightarrow \delta^{*}(q,\epsilon) \]
        Als het geen $\epsilon$-boog is, volg dan bestaat er een string $w$ die de DFA niet in een zelfde soort toestand brengen.
        \[ \exists w\in \Sigma^{*}:\ \delta^{*}(p,w) \in F \not\Leftrightarrow \delta^{*}(q,w) \]
        Dit omdat die string $w$ de DFA in respectievelijke toestanden zou brengen waartussen in $G$ een $\epsilon$-boog is.
        \[ \exists w\in \Sigma^{*}:\  \delta^{*}(p_{w},\epsilon) \in F \not\Leftrightarrow \delta^{*}(q_{w},\epsilon) \]
      \item \framebox{$\Leftarrow$}\\
        Als $p$ en $q$ $f$-verschillend zijn, dan bestaat er een string $w\in \Sigma^{*}$ die de DFA vanuit $p$ in een aanvaarbare toestand brengt, maar $q$ niet of omgekeerd.
        \[ \exists w \in \Sigma^{*}: \delta^{*}(p,w) \in F \not\Leftrightarrow \delta^{*}(q,w) \]
        Als die string $w$ leeg is, dan bestaat er sinds de initialisatiestap al een boog tussen $q$ en $w$. Als die string niet leeg is, dan kan $w$ geschreven worden als $w = vz$ met $v$ het eerste deel van $w$ en $z$ een symbool.
        \[ \exists v\in \Sigma^{*}, z \in \Sigma: w = vz \]
        Nu geldt het volgende:\footnote{Zie stelling \ref{st:delta-ster-identiteit}.}
        \[ \delta^{*}(p,w) = \delta(\delta^{*}(p,v),z) \text{ en } \delta^{*}(q,w) = \delta(\delta^{*}(q,v),z)\]
        Er is dus een boog tussen $\delta^{*}(p,v)$ en $\delta^{*}(q,v)$ dankzij de ``repeat'' stap.
        Dit betekent dat we het laatste symbool weer kunnen schrappen tot we uitkomen op een boog tussen $\delta^{*}(p,\epsilon)$ en $\delta^{*}(q,\epsilon)$ door van achter naar voor te werken.
      \end{itemize}
    \end{itemize}
  \end{proof}
\end{st}

\begin{de}
  Een DFA $D = (Q,\Sigma,\delta,q_{s},F)$ is \emph{minimaal} als er geen DFA $D'$ bestaat met \textit{strikt} minder toestanden.
\end{de}

\begin{st}
  Als een DFA $(Q,\Sigma,\delta,q_{s},F)$ geen onbereikbare toestanden heeft, en elke twee toestanden $f$-verschillend zijn, dan bestaat er geen machine met strikt minder toestanden die dezelfde taal bepaalt.

  \begin{proof}
    Bewijs uit het ongerijmde.\\
    Zij $D = (Q,\Sigma,\delta,q_{s},F)$ een DFA zonder onbereikbare toestanden, waarbij elke twee toestanden $f$-verschillend zijn.
    Stel nu dat er een DFA $D' = (Q',\Sigma,\delta',p_{s},F')$ bestaat die strikt minder toestanden heeft dan $D$. We bewijzen nu dat er dan minstens \'e\'en string is waarwoor $D$ niet in dezelfde soort toestand eindigt als in $D'$.
    
    Elke toestand van $D$ is bereikbaar.
    Er bestaat dus een string voor elke toestand die een pad naar die toestand zou volgen.
    \[ \forall q\in Q, \exists s\in \Sigma^{*}:\ \delta^{*}(q_{s},s) = q \]
    Omdat $D'$ minder toestanden heeft dan $D$ moet er minstens twee van de strings die in $D$ in verschillende toestanden zouden eindigen in dezelfde toestand eindigen.
    \[ \exists s_{1},s_{2} \in \Sigma: (\delta^{*}(q_{s},s_{1}) \neq \delta^{*}(q_{s},s_{2})) \wedge (\delta'^{*}(p_{s},s_{1}) = \delta'^{*}(p_{s},s_{2})) \]
    Vermits die toestanden van $D$ $f$-verschillend zijn bestaat er een string $v\in \Sigma^{*}$ die de machine vanuit die toestanden niet in dezelfde soort toestand brengt:
    Noem die staten $\delta^{*}(q_{s},s_{1}) = q_{1}$ en $\delta^{*}(q_{s},s_{2}) = q_{2}$.
    \[ (\delta^{*}(q_{1},v) \in F) \oplus (\delta^{*}(q_{2},v) \in F) \]
    Dit houdt precies het volgende in:
    \[ (\delta^{*}(q_{s},s_{1}v) \in F) \oplus (\delta^{*}(q_{s},s_{2}v) \in F) \]
    $D$ accepteert dus precies \'e\'en van de twee strings $s_{1}v$ en $s_{2}v$.
    We bekijken nu wat $D'$ met deze strings zou doen.
    \[ \delta'^{*}(p_{s},s_{1}v) = \delta'^{*}(\delta'^{*}(p_{s},s_{1}),v) = \delta'^{*}(\delta'^{*}(p_{s},s_{2}),v) = \delta'^{*}(p_{s},s_{2}v) \]
    $D'$ zou ofwel zowel $s_{1}v$ als $s_{2}v$ accepteren, ofwel geen van beide.
    In beide gevallen is dit niet hetzelfde gedrag als $D$.
    $D$ en $D'$ kunnen dus niet dezelfde taal bepalen.
  \end{proof}
\end{st}

\begin{gev}
  We kunnen de minimale DFA $D = (Q,\Sigma,\delta,q_{s},F)$ van $D' = (Q',\Sigma,\delta',q_{s}',F')$ dus construeren nadat we $Q'$ hebben gepartitioneerd in disjuncte deelverzamelingen van $f$-gelijke toestanden.

  \begin{proof}
    Bekijk de partitie $P = \{Q_{1},\dotsc,Q_{n}\}$ van $Q'$ als de nieuwe verzameling staten.
    \[ Q = P \]
    De nieuwe overgangsfunctie ziet er nu als volgt uit:
    \[ \forall a \in \Sigma:\ \delta(Q_{i},a) = Q_{j} \text{ zodat } \exists q \in Q_{j}:\ \delta(q,a) \in Q_{j} \]
    Het maakt niet uit welke $q\in Q_{j}$ er gekozen werd omdat voor elke keuze van $q$ $\delta(q,a)$ in dezelfde deelverzameling van $P$ zit (anders zouden de toestanden in $Q_{j}$ $f$-verschillend zijn).
    De nieuwe starttoestand is de verzameling waar $q_{s}$ in zit.
    \[ q_{s} \in q_{s}'\]
    $F$ is nu de unie van de verzamelingen van aanvaardbare staten $F$ van $D'$.
    $D$ bepaalt nu dezelfde taal als $D'$.
    Dat de staten in elke $Q_{i}$ $f$-gelijk zijn maakt immers net dat het niet uitmaakt in welke van de staten $Q_{i}$ de automaat een string afgaat.
    Alle toestanden van $D$ zijn nu dus onderling $f$-verschillend.
    Als de toestanden $Q_{i}$ immers $f$-gelijk waren, dan waren het geen verschillende verzamelingen geworden in het algoritme om $Q$ te partitioneren.
    Bijgevolg is $D$ minimaal.
  \end{proof}
\end{gev}

\begin{de}
  Twee DFA's $(Q_{1},\Sigma,\delta_{1},q_{s1},F_{1})$ en $(Q_{2},\Sigma,\delta_{2},q_{s2},F_{2})$ zijn isomorf als er een bijectie $b:\ Q_{1} \rightarrow Q_{2}$ bestaat zodat de volgende beweringen gelden:
  \begin{itemize}
  \item $b(F_{1}) = F_{2}$
  \item $b(q_{s1}) = q_{s2}$
  \item $b(\delta_{1}(q,a)) = \delta_{2}(b(q),q)$
  \end{itemize}
  Twee isomorfe DFA's bepalen bovendien dezelfde taal.
\end{de}


\subsection{Myhill-Nerode relaties op $\Sigma$}
\label{sec:myhill-nerode-relaties}

\subsubsection{Partities van $\Sigma^{*}$}
\label{sec:partities-van-sigma-ster}

\begin{de}
  Definieer de functie $reach(q)$ van een DFA $(Q,\Sigma,\delta,q_{s},F)$ als alle strings waarvoor de automaat in staat $q\in Q$ belandt.
  \[
  reach(q) = \{ w \in \Sigma^{*}\ |\ \delta^{*}(q_{s},w) = q \}
  \]
\end{de}

\begin{st}
  De taal $reach(q)$ van een DFA $D = (Q,\Sigma,\delta,q_{s},F)$ is regulier voor elke $q$.
  
  \begin{proof}
    Inderdaad, construeer een nieuwe automaat $D'$ vanuit $D$ waarin enkel $q$ een accepterende eindtoestand is.
    $reach(q)$ is nu de taal bepaald door $D'$. $D'$ aanvaardt immers enkel de strings waarvoor $D$ (en dus $D'$, want we hebben $\delta$ niet veranderd) in $q$ zou belanden.
  \end{proof}
\end{st}

\begin{st}
  De verzameling $R$ is een partitie van $\Sigma^{*}$ als elke toestand bereikbaar is.
  \[ R = \{ reach(q)\ |\ q \in Q \} \]

  \begin{proof}
    Kies een willekeurige DFA $D = (Q,\Sigma,\delta,q_{s},F)$ en een staat $q\in Q$.
    We gaan elke eigenschap van een partitie na.\deref{de:partitie}
    \begin{itemize}
    \item $reach(q)$ is niet leeg.\\
      We moeten er hier van uitgaan dat de overgangsfunctie $\delta$ van $D$ totaal is.
      Dit kunnen we zonder verlies van algemeenheid.\stref{st:dfa-totale-overgangsfunctie}
      Elke string $s\in \Sigma^*$ die we als invoer kunnen geven aan $D$ belandt zeker in een staat $q'$ zonder dat de automaat vast loopt.
      Nu geldt dat elke staat bereikt zal worden door minstens \'e\'en string als elke toestand bereikbaar is.
      $D$ kan immers ook gezien worden als een NFA zonder $\epsilon$ bogen (etc...). Wanneer we die NFA omzetten naar een reguliere expressie via een GNFA krijgen we een reguliere expressie zonder $\phi$'s. Er bestaat dus altijd minstens \'e\'en string die in $q$ belandt voor elke $q$.
    \item De verzamelingen in $R$ zijn onderling disjunct.
      Deze uitspraak is equivalent met de volgende: ``De DFA kan slechts in \'e\'en toestand belanden voor elke string $s\in\Sigma^{*}$''. Dit klopt omdat we het over \emph{deterministische} automaten hebben.
    \item De unie van alle verzamelingen in $R$ vormt $\Sigma^{*}$.
      Deze uitspraak is equivalent met de volgende: ``Er zijn geen strings $s\in \Sigma^{*}$ waarvoor de DFA $D$ niet in een staat van $Q$ belandt.''
      Inderdaad, het resultaat de overgangsfunctie $\delta$ blijft steeds binnen $Q$ als ze totaal is.
    \end{itemize}
  \end{proof}
\end{st}

\begin{gev}
  De partitie $R$ bepaalt de Equivalentierelatie ``voor zowel A als B belandt de automaat $D$ in dezelfde staat $q$'': $\sim_{D}$.
  \[ x \sim_{D} y \Leftrightarrow \delta^{*}(q_{s},x) = \delta^{*}(q_{s},y) \]

  \begin{proof}
    Inderdaad, $R$ is een partitie en elke partitie bepaalt een equivalentierelatie.\footnote{Zie stelling \ref{st:verband-partitie-equivalentierelatie}.}
  \end{proof}
\end{gev}

\begin{opm}
  De functie $reach(q)$ valt ook te definieren voor NFA's, maar dan vormt $R = \{ reach(q)\ |\ q \in Q \}$ geen partitie.
  Deze functie is dan niet echt interessant.
\end{opm}

\begin{ei}
  \label{ei:sim-dfa-rechts-congruent}
  De equivalentierelatie $\sim_{D}$ bepaald door $R = \{ reach(q)\ |\ q \in Q \}$ bij een DFA $(Q,\Sigma,\delta,q_{s},F)$ is rechts congruent:
  \[ \forall x,y \in \Sigma^{*},\ a \in \Sigma:\ (x \sim_{D} y) \Rightarrow (xa \sim_{D} ya) \]
  \begin{proof}
    $x \sim_{D} y$ betekent dat de automaat $D$ bij input string $x$ en $y$ in dezelfde staat belandt.
    \[ \delta^{*}(q_{s},x) = \delta^{*}(q_{s},y) \]
    Omdat de automaat $D$ deterministisch is, zal de automaat bij input string $xa$ en $ya$ dan ook in dezelfde (maar mogelijk een andere dan voorheen) staat belanden.\stref{st:delta-ster-identiteit}
    \[
    \begin{array}{rll}
      \delta^{*}(q_{s},(xa)) &= \delta(\delta^{*}(q,x),a) &\\
      &= \delta(\delta^{*}(q,y),a) &= \delta^{*}(q_{s},(ya))
    \end{array}
    \]
  \end{proof}
\end{ei}

\begin{ei}
  \label{ei:sim-dfa-verfijnt-sim-l}
  De partitie $R = \{ reach(q)\ |\ q \in Q \}$ bij een DFA $(Q,\Sigma,\delta,q_{s},F)$ verfijnt $\sim_{L}$.
  \[ \forall x,y \in \Sigma^{*}, \forall L\in \mathcal{P}(\Sigma^{*}):\ x \sim_{DFA} y \Rightarrow x \sim_{L} y\]
  \begin{proof}
    Inderdaad, als voor twee strings $x \sim_{D} y$ geldt, dan zitten $x$ en $y$ in $L_{DFA}$ als en slechts als de staat $q$ waarin de automaat belandt door $x$ (en $y$) aanvaardbaar is.
  \end{proof}
\end{ei}

\begin{ei}
  \label{ei:sim-dfa-eindig-aantal-equivalentieklassen}
  De equivalentierelatie $\sim_{D}$ door bepaald door $R = \{ reach(q)\ |\ q \in Q \}$ bij een DFA $(Q,\Sigma,\delta,q_{s},F)$ heeft een eindig aantal equivalentieklassen.
  \begin{proof}
    Het aantal equivalentieklassen van $\sim_{D}$ is precies gelijk aan het aantal staten in $Q$ van de automaat $D$. Omdat $D$ een \emph{eindige} automaat is, is dit dus een eindig aantal.
  \end{proof}
\end{ei}

\begin{de}
  \label{de:mn-relatie}
  Een \term{Myhill-Nerode relatie} voor een taal $L$ over een alfabet $\Sigma$ is een equivalentierelatie $\sim$ op $L$ met de volgende eigenschappen:
  \[ \sim \subseteq L \times L:\ l_{1} \sim_{DFA} l_{2}\]
  \[ \sim \text{ is } MN(L) \]
  \begin{itemize}
  \item $\sim$ is rechts congruent:
    \[ \forall x,y \in \Sigma^{*}, a \in \Sigma:\ x \sim y \Rightarrow (xa) \sim (ya) \]
  \item $\sim$ verfijnt $\sim_{L}$:
    \[ \forall x,y \in \Sigma^{*}, \forall L\in \mathcal{P}(\Sigma^{*}):\ x \sim y \Rightarrow x \sim_{L} y\]
    In woorden: ``Als $x \sim y$ geldt, zitten ofwel zowel $x$ als $y$ in $L$, ofwel geen van beide.''
    Of nog: ``De partitie bepaald door $\sim$ is fijner dan de partitie bepaald door $\sim_{L}$.''
  \item Het aantal equivalentieklassen van $\sim$ is eindig.
    We zeggen: ``De index van $\sim$ is eindig.''.
  \end{itemize}
\end{de}

\begin{st}
  \label{st:dfa-naar-mn-relatie}
  Gegeven een DFA $D = (Q,\Sigma,\delta,q_{s},F)$ bestaat er een $MN(L_{D})$ relatie $\sim$ over $L$:
  \[ \forall x,y \in \Sigma^{*}: x \sim_{D} y \Leftrightarrow \delta^{*}(q_{s},x) = \delta^{*}(q_{s},y) \Leftrightarrow reach(x) = reach(y) \]
  In woorden: ``De DFA belandt voor de strings $x$ en $y$ in dezelfde toestand.''
  \begin{proof}
    Inderdaad, deze relatie is rechts-congruent\eiref{ei:sim-dfa-rechts-congruent}, verfijnt $\sim_{L}$\eiref{ei:sim-dfa-verfijnt-sim-l} en heeft een eindig aantal equivalentieklassen\eiref{ei:sim-dfa-eindig-aantal-equivalentieklassen}.
  \end{proof}
\end{st}

\begin{de}
  We noteren de equivalentieklasse van $x$ in een Myhill-Nerode relatie $\sim$ als $x_{\sim}$.
  \[ x_{\sim} = \{ y\ |\ x \sim y \} \]
\end{de}

\begin{st}
  \label{st:mn-relatie-naar-dfa}
  Gegeven een taal $L$ over $\Sigma$ en een MN($L$)-relatie $\sim$ op $\Sigma^{*}$, dan is $D = (Q,\Sigma,\delta,q_{s},F)$ een DFA die $L$ bepaalt:
  \begin{itemize}
  \item $Q = \{ x_{\sim}\ |\ x \in \Sigma^{*} \}$: Elke equivalentieklasse is een toestand.
  \item $q_{s} = \epsilon_{\sim}$: De starttoestand bereik je met $\epsilon$.
  \item $F = \{ x_{\sim}\ |\ x\in L \}$: Een eindtoestand wordt bereikt door een string in $L$.
  \item $\delta:\ \mathcal{P}(\Sigma^{*})\times\Sigma   \rightarrow \mathcal{P}(\Sigma^{*}):\ \delta(x_{\sim},a) = (xa)_{\sim}$.
  \end{itemize}
  \begin{proof}
    $\delta$ is goed gedefinieerd vanwege de rechtse conguentie van de relatie $\sim$.\deref{de:mn-relatie}
    Zowel $Q$ als $F$ zijn eindig omdat het aantal equivalentieklassen van $\sim$ eindig is.
    Er rest ons nu nog te bewijzen dat $D$ de taal $L$ bepaalt.
    \[ \forall x\in \Sigma^{*}:\ \delta^{*}(e_{\sim},x) \in F \Leftrightarrow x_{\sim} \in F\]
    We bewijzen dit met inductie op de lengte van een willekeurige string $x$.
    Als de lengte van $x$ $0$ is, geldt de bewering:
    \[ \delta^{*}(e_{\sim},x) = \delta^{*}(e_{\sim},\epsilon) = e_{\sim} \in F \Leftrightarrow \epsilon_{\sim} \in F \]
    Stel dat de bewering geldt voor een bepaalde lengte van $x$, dan geldt ze ook voor $xa$ met $a$ een symbool:
    \[ \delta^{*}(e_{\sim},xa) = \delta(x_{\sim},a) = (xa)_{\sim} \in F \Leftrightarrow (xa)_{\sim} \in F \]
  \end{proof}
\end{st}

%\begin{st}
%  De overgangen van DFA naar MN relatie\stref{st:dfa-naar-mn-relatie} en van daar naar een DFA\stref{st:mn-relatie-naar-dfa} zijn elkaars inversen op een DFA-isomorfisme na.
%  \extra{formeler en bewijs}
%\end{st}

%\begin{st}
%  Twee DFA's zijn isomorf als en slechts als ze dezelfde $\sim_{DFA}$ hebben.
%  \extra{formeler en bewijs}
%\end{st}

\begin{st}
  \label{st:oneindig-veel-dfas-voor-een-taal}
  Er bestaat oneindig veel niet-isomorfe DFA's die een reguliere taal $L$ aanvaarden.

  \begin{proof}
    Inderdaad, voor een reguliere taal $L$ bestaat er steeds een DFA\gevref{gev:reguliere-taal-DFA}.
    Voeg nu aan die DFA een staat toe en voeg aan $\delta$ een boog toe van de `trash'-staat naar de nieuwe staat.
    De bogen in de originele automaat van de `trash'-staat naar zichzelf moeten mogelijks verwijderd worden.
    De nieuwe DFA is nu niet isomorf met de originele DFA, maar bepaalt wel dezelfde taal.
    Deze redenering kan men bovendien herhalen tot in het oneindige.
  \end{proof}
\end{st}

\subsubsection{Het supremum van twee $MN(L)$ relaties}
\label{sec:het-supremum-van}

\begin{de}
  Het supremum $\sim_{sup}$ van twee $MN(L)$ relaties $\sim_{1}$ en $\sim_{2}$ is de transitieve sluiting van $x \sim_{1 \vee 2} y \Leftrightarrow (x \sim_{1} y) \vee (x \sim_{2} y)$.
  \[ x\sim_{sup}y \Leftrightarrow \exists z_{1},\dotsc,z_{n-1}:\ x\sim_{1 \vee 2}z_{1} \wedge z_{1}\sim_{1 \vee 2}z_{2} \wedge \dotsb \wedge z_{n-1} \sim_{1 \vee 2} y \]
\end{de}

\begin{st}
  Het supremum van twee $MN(L)$-relaties is ook een $MN(L)$-relatie.

  \begin{proof}
    We gaan elke eigenschap van een $MN(L)$-relatie na.
    \begin{itemize}
    \item $\sim_{sup}$ is rechts congruent:\\
      \[
      \begin{array}{l}
      x\sim_{sup}y\\
      \Leftrightarrow \exists z_{1},\dotsc,z_{n-1}:\ x\sim_{1 \vee 2}z_{1} \wedge \dotsb \wedge z_{n-1} \sim_{1 \vee 2} y\\
      \Leftrightarrow \exists z_{1},\dotsc,z_{n-1}:\ ((x \sim_{1} z_{1}) \vee (x \sim_{2} z_{1})) \wedge \dotsb \wedge ((z_{n-1} \sim_{1} y) \vee (z_{n-1} \sim_{2} y))\\
      \Rightarrow \exists x_{1},\dotsc,x_{n-1}:\ \forall a \in \Sigma:\ ((xa \sim_{1} z_{1}a) \vee (xa \sim_{2} z_{1}a)) \wedge \dotsb \wedge ((z_{n-1}a \sim_{1} ya) \vee (z_{n-1}a \sim_{2} ya))\\
      \Leftrightarrow \exists z_{1},\dotsc,z_{n-1}:\ \forall a \in \Sigma:\ xa\sim_{1 \vee 2}z_{1}a \wedge \dotsb \wedge z_{n-1}a \sim_{1 \vee 2} ya\\
      \Leftrightarrow \forall a \in \Sigma:\ xa \sim_{sup} ya\\
      \end{array}
      \]
    \item $\sim_{sup}$ verfijnt $\sim_{L}$:\\
      Zij $x$ een string in $L$ en $x\sim_{sup}y$:
      \[
      \begin{array}{l}
        x\sim_{sup}y\\
        \Leftrightarrow \exists z_{1},\dotsc,z_{n-1}:\ x\sim_{1 \vee 2}z_{1} \wedge \dotsb \wedge z_{n-1} \sim_{1 \vee 2} y\\
        \Leftrightarrow \exists z_{1},\dotsc,z_{n-1}:\ ((x \sim_{1} z_{1}) \vee (x \sim_{2} z_{1})) \wedge \dotsb \wedge ((z_{n-1} \sim_{1} y) \vee (z_{n-1} \sim_{2} y))\\
        \Rightarrow (z_{1} \in L) \wedge \exists z_{2},\dotsc,z_{n-1}:\ ((z_{1} \sim_{1} z_{2}) \vee (z_{1} \sim_{2} z_{2})) \wedge \dotsb \wedge ((z_{n-1} \sim_{1} y) \vee (z_{n-1} \sim_{2} y))\\
        \Rightarrow (z_{2} \in L) \wedge \exists z_{3},\dotsc,z_{n-1}:\ ((z_{2} \sim_{1} z_{3}) \vee (z_{2} \sim_{2} z_{3})) \wedge \dotsb \wedge ((z_{n-1} \sim_{1} y) \vee (z_{n-1} \sim_{2} y))\\
        \vdots\\
        \Rightarrow (z_{n-2} \in L) \wedge \exists z_{n-1}:\ ((z_{n-2} \sim_{1} z_{n-1}) \vee (z_{n-2} \sim_{2} z_{n-1})) \wedge ((z_{n-1} \sim_{1} y) \vee (z_{n-1} \sim_{2} y))\\
        \Rightarrow (z_{n-1} \in L) \wedge ((z_{n-1} \sim_{1} y) \vee (z_{n-1} \sim_{2} y))\\
        \Rightarrow y \in L
      \end{array}
      \]
    \item Het aantal equivalentieklassen van $\sim_{sup}$ is eindig want dat aantal is hoogstens zo groot als het aantal equivalentieklassen van $\sim_{1}$ en $\sim_{2}$.
      %\clarify{waarom?}
    \end{itemize}
  \end{proof}
\end{st}

\subsubsection{$MN(L)$ gebruiken om te bewijzen dat een taal niet regulier is}
\label{sec:mnl-gebruiken-om}

\begin{st}
\label{st:an-bn-niet-regulier-mn-relatie}
  De taal $L= \{ a^{n}b^{n} \ |\ n\in \mathbb{N} \} $ is niet regulier.

  \begin{proof}
    Stel dat er een equivalentierelatie $\sim$ bestaat voor $L$ die zowel rechts-congruent is als $\sim_{L}$ verfijnt en afkomstig is van de minimale DFA van $L$, dan bewijzen we nu dat deze equivalentierelatie een oneindig aantal equivalentieklassen heeft en bijgevolg geen $MN(L)$-relatie kan zijn.
    De taal $L$ is dan zeker niet regulier.
    Beschouw de equivalentieklassen van $\sim$.
    Voor elke $n\in \mathbb{N}$ moet de string $a^{n}$ in een andere klasse zitten, want voor elke $n$ is er een ander aantal $b$'s dat de automaat in $F$ brengt.
    Er zijn dus oneindig veel equivalentieklassen.
  \end{proof}
\end{st}

\subsubsection{De stelling van Myhill-Nerode}
\label{sec:de-stelling-van}

\begin{st}
  De \term{stelling van Myhill-Nerode}\\
  Zij $L\subseteq \Sigma^{*}$ een taal over $\Sigma$, dan zijn de volgende uitspraken equivalent.
  \begin{itemize}
  \item $L$ is regulier.
  \item Er bestaat een Myhill-Nerode relatie voor $L$.
  \item Definieer $\sim$ op $\Sigma^{*}$ als volgt, dan heeft $\sim$ een eindige index.
    \[ x \sim y \Leftrightarrow \forall s \in \Sigma^{*}:\ (xs \in L \Leftrightarrow ys \in L) \]
  \end{itemize}
  \zb
\end{st}


\subsection{De minimale DFA}
\label{sec:de-minimale-dfa}

\begin{de}
  \label{de:supremum-dfas}
  Het supremum $D_{sup}$ van twee DFA's $D_{1}$ en $D_{2}$ is de DFA waarvoor de $MN(L)$-relatie het supremum is van de $MN(L)$-relaties van $D_{1}$ en $D_{2}$.
\end{de}

\begin{st}
  \label{st:minimale-dfa-uniek}
  De minimale DFA voor een taal $L$ is uniek op isomorfisme na.
  
  \begin{proof}
    Bewijs uit het ongerijmde.\\
    Stel dat er twee verschillende, niet isomorfe minimale DFA's bestaan die dezelfde taal $L$ bepalen, dan hebben die hetzelfde aantal elementen.
    Zij $N$ het aantal staten van de twee DFA's.
    Neem nu het supremum $D_{sup}$ van de twee DFA's.
    Je krijgt een DFA met opnieuw $N$ toestanden.
    Meer kan niet, want anders zou het niet het supremum zijn, maar minder kan ook niet, want dan zouden de originele DFA's niet minimaal zijn.
    De drie $MN(L)$ relaties zijn dus identiek, wat betekent dat de DFA's isomorf zijn.
  \end{proof}
\end{st}

\subsection{Het pompen van strings in reguliere talen}
\label{sec:het-pompend-van}

\begin{lem}
  Het \term{pompend lemma} voor reguliere talen\\
  Voor een reguliere taal $L$ bestaat er een pomplengte $d$ zodat als een er string in $L$ zit die langer is dan $d$, er een verdeling van $s$ bestaat in stukken $x$, $y$ en $z$.
  \[ s = xyz \]
  \begin{itemize}
  \item $\forall i \in \mathbb{N}_{0}:\ xy^{i}z \in L$
  \item $|y| > 0$
  \item $|xy| \le d$
  \end{itemize}

  \begin{proof}
    Kies een DFA $D$ die een een reguliere taal $L$ bepaalt.
    $d$ zal $|Q| + 1$ zijn:
    Neem een willekeurige string $s\in L = a_{1}a_{2}\ldots a_{n}$ langer dan $d$.
    Er bestaat dan een opeenvolging van toestanden $X$ die $D$ zou doorlopen om $s$ te accepteren.
    \[ X = q_{s}q_{1}q_{2}q_{3}\ldots q_{n} \]
    Deze opeenvolging heeft een lengte $n$ strikt groter dan $n$, dus er zijn bij de eerste $d$ toestanden zeker twee toestanden gelijk.
    Stel nu dat $q_{i}$ en $q_{j}$ twee gelijke toestanden zijn met $i < j \le d$, dan zijn $x$, $y$ en $z$ als volgt:
    \[
    \begin{array}{rl}
      x &= a_{1}a_{2}\ldots a_{i}\\
      y &= a_{i+1}a_{i+2}\ldots a_{j}\\
      z &= a_{j+1}a_{j+2}\ldots a_{n}\\
    \end{array}
    \]
    De lus die $y$ volgt kunnen we inderdaad zoveel keer overlopen als nodig, zodat voor elke x $xy^{x}z$ aanvaardt wordt.
    De lengte van $y$ is groter dan nul omdat $i < j$ geldt, en we hebben $|xy|$ kleiner dan $d$ gekozen.
  \end{proof}
\end{lem}

\begin{st}
\label{st:an-bn-niet-regulier-pompend-lemma}
  De taal $L= \{ a^{n}b^{n} \ |\ n\in \mathbb{N} \} $ is niet regulier.

  \begin{proof}
    Stel dat $L$ regulier is, dan bestaat er een pomplengte $d$.
    Beschouw nu een string $s$ langer dan $d$: $a^{d}b^{d}$.
    Neem een willekeurige opdeling van $s$ in stukken $xyz$ met $|y| > 0$.
    Er zijn nu drie mogelijkheden:
    \begin{enumerate}
    \item $y$ bevat enkel $a$'s.\\
      $xyyz$ bevat dan meer $a$'s dan $b$'s en zit bijgevolg niet in $L$.
    \item $y$ bevat zowel $a$'s als $b$'s.\\
      In $xyyz$ staan dan niet alle $a$'s voor de $b$'s, dus $xyyz$ zit niet in $L$.
    \item $y$ bevat enkel $b$'s\\
      $xy^{0}z = xz$ bevat dan meer $a$'s dan $b$'s en zit dus ook niet in $L$.
    \end{enumerate}
    Eigenlijk konden we de laatste twee mogelijkheden meteen schrappen want in die gevallen zou $xy$ kleiner zijn dan $d$.
  \end{proof}
\end{st}

\subsection{De algebra van DFA's}
\label{sec:de-algebra-van-DFAs}

\begin{de}
  De \term{product DFA} $D = (Q,\Sigma, \delta, q_{s},F)$ van twee DFA's $D_{1} = (Q_{1},\Sigma, \delta_{1}, q_{s1},F_{1})$ en $D_{2} = (Q_{2},\Sigma, \delta_{2}, q_{s2},F_{2})$ definieren we als volgt:
  \begin{itemize}
  \item $Q = Q_{1}\times Q_{2}$
  \item $\delta((p, q),x) = \delta_{1}(p,x) \times \delta_{2}(q,x)$
  \item $q_{s} = (q_{s1}, q_{s2})$
  \end{itemize}
\end{de}

\begin{de}
  De \term{doorsnede van DFA's} $D_{1}$ en $D_{2}$ is de DFA $D$ die de doorsnede bepaalt van de talen bepaald door $D_{1}$ en $D_{2}$.
  \[ D_{1} \times D_{2} \text{ met } F = F_{1} \times F_{2} \]
\end{de}

\extra{ De doornsede van twee DFA's bepaalt de doorsnede van de talen. bewijs}

\begin{de}
  De \term{unie van DFA's} $D_{1}$ en $D_{2}$ is de DFA $D$ die de unie bepaalt van de talen bepaald door $D_{1}$ en $D_{2}$.
  \[ D_{1} \times D_{2} \text{ met } F = (F_{1}\times Q_{2}) \times (F_{2} \times Q_{1}) \]
\end{de}

\extra{ De unie van twee DFA's bepaalt de unie van de talen. bewijs}

\begin{de}
  Het \term{complement van een DFA} $D = (Q,\Sigma, \delta, q_{s},F)$ is de DFA $D^{c} = (Q,\Sigma, \delta, q_{s},Q\setminus F)$ die het complement bepaalt van de taal bepaald door $D$.
\end{de}

\extra{bewijs}

\begin{de}
  \label{de:symmetrisch-verschil-dfas}
  Het \term{symmetrisch verschil van DFA's} $D_{1}$ en $D_{2}$ is de DFA $D$ die het symmetrisch verschil bepaalt van de talen bepaald door $D_{1}$ en $D_{2}$.
  \[ D_{1} \times D_{2} \text{ met } F = (Q_{1}\setminus F_{1}) \times (Q_{2}\setminus F_{2}) \]
\end{de}

\extra{bewijs}
\end{document}