\documentclass[12pt, a4paper, titlepage]{extarticle}
\usepackage[dutch]{babel}
\selectlanguage{dutch}
\usepackage[utf8]{inputenc}
\usepackage{hyperref}
\hypersetup{
    colorlinks,
    citecolor=hdrie,
    filecolor=hdrie,
    linkcolor=hdrie,
    urlcolor=hdrie
}
\usepackage{amsmath}
\usepackage{framed}
\usepackage{amsthm}
\usepackage{tikz}
\usetikzlibrary{automata,positioning}
%\usepackage{fontspec}
%\newfontfamily\headingfont[]{BerninoSansOffcBold.otf}
%\newfontfamily\sectionfont[]{BerninoSansOffcSb.otf}
%\newfontfamily\subsectionfont[]{BerninoSansOffc.otf}
%\newfontfamily\subsubsectionfont[]{freight-text-bold.otf}
%\usepackage{titlesec}
%\usepackage{titling}
%\titleformat*{\section}{\color{hdrie}\LARGE\sectionfont}
%\titleformat*{\subsection}{\color{hvier}\Large\subsectionfont}
%\titleformat*{\subsubsection}{\color{hdrie}\large\subsubsectionfont}
%\renewcommand{\maketitlehooka}{\color{hdrie}\huge\headingfont}
\usepackage{color}
\definecolor{hdrie}{gray}{0.2}
\definecolor{hvier}{gray}{0.56}
\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{enumerate}
\usepackage{lmodern}
\usepackage[linesnumbered,onelanguage,ruled,lined]{algorithm2e}
\usepackage{float}
\usepackage{extarrows}

%\setmainfont[
% BoldFont={freight-text-bold.otf}, 
% ItalicFont={freight-text-italic.otf}
% ]{freight-text-book.ttf}

%\renewcommand{\rmdefault}{cmr}

\theoremstyle{definition}
\newtheorem{definition}{Theoretische Zever}[subsection]

\theoremstyle{definition}
\newtheorem{remark}{Vage Opmerking}[subsection]

\setcounter{section}{-1}

\begin{document}
	\title{FVI}
	\color{hdrie}
	\maketitle
	
	\tableofcontents
	\pagebreak
	
	\section{Intro}
	\subsection{Inhoud}
	\begin{enumerate}
		\item (H2) Herhaling: verzamelingen, ...
		\item (H3) Strings, talen
		\item (H4) Grafen
		\item (H5) Vastpuntstheorie
	\end{enumerate}
	\subsection{Evaluatie: examen}
	\begin{itemize}
		\item Helft theorie, helft oef
		\item Gesloten boek
		\item Bewijzen kennen
	\end{itemize}
	
	% Talen, automaten, berekenbaarheid
	\pagebreak
	\setcounter{section}{2}
	\section{Talen, automaten, berekenbaarheid}
	\subsection{Strings \& talen}
	\begin{leftbar}
	\begin{description}
		\item[Alfabet] Een eindige, niet-lege verzameling. De elementen van deze verzameling worden symbolen genoemd.\\
			\textit{e.g.:} $\Sigma_1 = {a, b, c}; \Sigma_2 = {0, 1, 2, ... 9}$ 
		\item[String] Een string over $\Sigma$ is een eindige rij symbolen uit $\Sigma$. $\lambda$ stelt de lege string voor. Het aantal symbolen in de string wordt de lengte genoemd, genoteerd $|s|$.\\
			\textit{Notatie} voor verzameling van alle strings over $\Sigma$: $\Sigma^*$.
		\item[Taal] Een taal over $\Sigma$ is een deelverzameling van $\Sigma^*$.\\
			\textit{e.g.:} $\Sigma = {a, b, ..., z}; T_1 = {ab, zot}; T_2 = {de, het, kat, ...}$ = alle NL woorden.
		\item[Algoritme] Een eindige rij eenduidige instructies die na elkaar worden uitgevoerd. De uitvoering eindigt steeds.
	\end{description}
	\end{leftbar}
	\subsubsection{Bewerkingen op strings}
	\begin{description}
		\item[Concatenatie] $S_1S_2$\\
			\textit{e.g.:} $ab\ ba \rightarrow abba$\\
			Als $x = \sigma_1\sigma_2\sigma_3...\sigma_n$ (met $\sigma_i \in \Sigma$)\\
			en $y = \tau_1\tau_2\tau_3...\tau_n$ (met $\tau_i \in \Sigma$\\
			dan is $xy = \sigma_1\sigma_2\sigma_3...\sigma_n\tau_1\tau_2\tau_3...\tau_n$.\\
			\textit{Note:} $x^0 = \lambda$
	\end{description}
	\subsubsection{Bewerkingen op talen}
	Zij $A \subseteq \Sigma^*, B \subseteq \Sigma^*$,\\
	dan is $AB = {st | s \in A, t \in B}$.\\
	$A^0 = {\lambda}$\\
	$\forall n > 0: A^n = AA^{n-1}$\\
	\[ A^* = A^0 \bigcup A \bigcup A^2 \bigcup A^3 \bigcup ... = \bigcup_{n=0}^{\infty} A^n \]
	($A^*$ is de \textbf{Kleene-sluiting} van A.)
	\begin{leftbar}
	\begin{definition}[\textit{Reguliere taal}] 
		Zij $\Sigma$ een alfabet, $R$ is een reguliere taal $\iff R \in \Re$. Met $\Re$ als volgt: 
		\begin{enumerate}
			\item $\varnothing \in \Re, \{\lambda \} \in \Re$ en $\forall \sigma \in \Sigma : \{ \sigma \} \in \Re$
			\item Indien $A, B \in \Re$, dan ook $AB \in \Re, A \bigcup B \in \Re$ en $A^* \in \Re$
		\end{enumerate} 
	\end{definition}
	\end{leftbar}
	\textbf{Let op!} De operaties zijn op talen, niet op strings.
	In verstaanbaar Nederlands:
	\begin{leftbar}
	Een taal $L \subseteq \Sigma^*$ is een reguliere taal als en slecht als ze kan opgebouwd worden vanuit $\varnothing, \{ \lambda \}$ en $\{ \sigma \} (\forall \sigma \in \Sigma)$ door een eindig aantal keer de bewerkingen “concatenatie”, … $\bigcup$ … en …$^*$ te gebruiken.
	\end{leftbar}
	\subsubsection{Reguliere expressie}
	\begin{leftbar}
	\begin{definition}[\textit{Reguliere expressie}] 
		Gegeven alfabet $\Sigma$. Dan $\varnothing$ is een r.e., $\lambda$ is een r.e., $\sigma (\sigma \in \Sigma)$ is een r.e..
		En als $A, B$ r.e. zijn, dan $(A), AB, A^*, A|B$ zijn ook r.e..\\
		\textit{e.g.:} $d(i|a)t$ = {dit, dat}
	\end{definition}
	\end{leftbar}
	\subsection{Eindige toestandsautomaten}
	Elke automaat komt overeen met een taal. Automaat is algoritme dat bepaalt of een inputstring deel is van de taal gerepresenteerd door de machine.
	\begin{leftbar}
	\begin{definition}[\textit{Eindige toestandsautomaat}]
		Een eindige automaat is een 5-tal $A = (Q, \Sigma, \delta, q_0, F)$. ($Q$: verzameling toestanden, $\Sigma$: alfabet, $\delta$: $Q \times \Sigma \to Q = $ transitieafbeelding, $q_0$: begintoestand, $F \in Q$: verzameling van aanvaardende toestanden).
	\end{definition}
	\end{leftbar}
	\subsubsection{Uitgebreide transitieafbeelding $\delta^*$}
	\begin{itemize}
		\item Een automaat $A$ aanvaardt een string $s \iff \delta^*(q_0, s) \in F$
		\item Taal bepaald door A = $L(A) = \{s \in \Sigma^*\ |\ \delta^*(q_0, s) \in F\} $
		\item Bij gegeven $T$ zeggen we dat $A$ de taal herkent $\iff L(A) = T$
		\item Elke string, herkend door een automaat, is altijd een reguliere taal. Voor elke reguliere taal bestaat er minstens 1 automaat die die taal herkent.
	\end{itemize}
	\subsubsection{NDFA — Non-Deterministic Finite State Automata}
	\begin{leftbar}
		\begin{definition}
			Een NDFA is een 5-tal $A = (Q, \Sigma, \delta, q_0, F)$ met:
			\begin{itemize}
				\item $Q$ een eindige verzameling (de ``toestanden''),
				\item $\Sigma$ een alfabet,
				\item $F \subseteq Q$ verzameling van aanvaardende toestanden,
				\item $q_0 \in Q$ de ``begintoestand'',
				\item $\delta$ een afbeelding $\delta : Q \times (\Sigma \bigcup \{\lambda\}) \to P(Q)$.
			\end{itemize}
		\end{definition}
	\end{leftbar}
	\subsection{Turingmachines}
	\subsubsection{Turingmachines}
	Eindige automaten zijn beperkt qua berekeningen (geen geheugencapaciteit): herkennen enkel reguliere talen. Turingmachines: ander wiskundig model, grote geheugencapaciteit. TM kan dezelfde rekentaken uitvoeren als een computer.\\
	\textbf{Model}:
	\begin{itemize}
		\item TM heeft magneetband (geheugen) die in 2 richtingen kan bewegen
		\begin{itemize}
			\item Deze bevat in verschillende fasen de input, tussenresultaten of output
			\item Is oneindig lange rij van symbolen, bestaat uit eindige string voorafgegaan en gevolgd door oneindig aantal blanco karakters
		\end{itemize}
		\item TM heeft lees-/schrijfkop
		\begin{itemize}
			\item Symbool op magneetband onder kop: \textbf{huidig symbool}
			\item Kop kan huidig symbool overschrijven
		\end{itemize}
		\item Eindig aantal mogelijke toestanden
		\item Instructies
		\begin{itemize}
			\item huidig symbool overschrijven
			\item kop (of magneetband, for that matter) 1 positie naar links of rechts bewegen
			\item naar een nieuwe toestand overgaan
		\end{itemize}
	\end{itemize}
	TM blijft instructies uitvoeren tot in toestand waarbij voor huidig symbool geen instructie voorhanden $\rightarrow$ controleren of in aanvaardbare eindtoestand.
	\begin{leftbar}
		\begin{definition}[\textit{Turingmachine}]
			Een Turingmachine is een 6-tal $M=(Q,\Sigma,T,P,q_0,F)$ met:
			\begin{itemize}
				\item $Q$ een eindige verzameling; we noemen de elementen van $Q$ \textbf{toestanden}
				\item $F \subset Q$ de verzameling van \textbf{aanvaardbare eindtoestanden}
				\item $q_0 \in Q$ de \textbf{begintoestand}
				\item $\Sigma$ het alfabet van de TM. Dit alfabet bevat, naast mogelijk andere symbolen, minstens een speciaal symbool, het \textbf{blancosymbool} of \textbf{lege symbool}, dat we noteren als $\#$.
				\item $T \subseteq \Sigma \backslash \{\#\}$ is de verzameling van \textbf{invoersymbolen}. De elementen van $\Sigma \backslash (T \bigcup \{\#\})$ worden \textbf{hulpsymbolen} genoemd.
				\item P een functie (niet noodzakelijk een afbeelding)
					\[ P:(Q\backslash F) \times \Sigma \rightarrow Q\times\Sigma\times\{L,R,0\} \]
					P wordt het \textbf{programma} of de \textbf{instructieset} van de TM genoemd. (In de verzameling ${L,R,0}$ staat $L$ voor ``Links'', $R$ voor ``Rechts'' en $0$ voor ``Blijf staan'', waarmee de beweging van de schrijfkop aangegeven wordt.)
			\end{itemize}
			\label{tm}
		\end{definition}	
	\end{leftbar}
	\textbf{Praktisch}:\\
	\begin{enumerate}
		\item TM start $\rightarrow$ begintoestand $q_0$ en kop boven meest linkse, niet blanco symbool van magneetband
		\item TM voert programma $P$ uit: noem $q$ de toestand waarin TM zich op bepaald moment bevindt en neem $\sigma \in \Sigma$ het symbool dat op dat moment door kop gelezen wordt.\\
			2 opties:
			\begin{itemize}
				\item $(q, \sigma) \in$ definitiegebied van functie $P \Rightarrow P(q, \sigma)$ bestaat en $= (q', \sigma', X)\in Q\times\Sigma\times\{L,R,0\}$.\\
					\textbf{Resultaat}: TM verandert toestand in $q'$, huidig symbool $\sigma$ vervangen door $\sigma'$, kop beweegt volgens $X$ (links, rechts, ter plaatse)
				\item $(q, \sigma) \notin$ definitiegebied van $P$.\\
					\textbf{Resultaat}: programma stopt. $q$ is eindtoestand van TM voor die bepaalde invoer.
			\end{itemize}
		\item TM gestopt en $q \in F\Rightarrow$ invoerstring aanvaard \& eindige string symbolen op magneetband is uitvoer van TM, in andere geval: string verworpen
	\end{enumerate}
	\subsubsection{Turingmachines en functies}
	Een functie is \textbf{effectief berekenbaar} als de functie berekenbaar is op een machine met onbegrensde opslagcapaciteit (TM).
	\begin{leftbar}
		\begin{definition}[\textit{These van Church}]
			Een functie is effectief berekenbaar als en slechts als die functie Turing-berekenbaar is.
		\end{definition}
	\end{leftbar}
	\begin{leftbar}
		\begin{definition}
			Er bestaat een functie $f:\mathbb{N}\rightarrow\mathbb{N}$ die niet Turing-berekenbaar is.
		\end{definition}
	\end{leftbar}
	\textbf{Bewijs}: zie cursus p.29.
	\subsubsection{Turingmachines en talen}
	TM aanvaardt inputstring als deze eindigt in aanvaardbare eindtoestand, anders verworpen. Taal bepaalt door TM is verzameling van alle strings die aanvaard worden.
	\begin{leftbar}
		\begin{definition}
			De taal \textbf{bepaald} door een Turingmachine $M$, genoteerd $L(M)$, is de verzameling van alle invoerstrings waarvoor $M$ in een aanvaardbare toestand eindigt. Gegeven een taal $L$, zeggen we dat $L$ \textbf{herkend} wordt door $M$ als $L(M) = L$.
		\end{definition}
	\end{leftbar}
	\begin{leftbar}
		\begin{definition}
			Een taal $L$ wordt \textbf{Turing-herkenbaar} genoemd, als er een TM bestaat die $L$ herkent. Turing-herkenbare talen worden ook \textbf{recursief opsombare} talen genoemd.
		\end{definition}
	\end{leftbar}
	\begin{leftbar}
		\begin{definition}
			Een TM \textbf{beslist} een taal, als voor elk string $s \in L$ de TM in een aanvaardbare toestand eindigt, en voor elke string $s \notin L$ de TM in een onaanvaardbare toestand eindigt.
		\end{definition}
	\end{leftbar}
	\begin{leftbar}
		\begin{definition}
			Een taal $L$ wordt \textbf{Turing-beslisbaar} of kortweg \textbf{beslisbaar} genoemd, als er een TM bestaat die $L$ beslist. Turing-beslisbare talen worden ook \textbf{recursieve} talen genoemd.
		\end{definition}
	\end{leftbar}
	\subsubsection{Niet-deterministische Turingmachines}
	\begin{leftbar}
		\begin{definition}[\textit{Niet-deterministische Turingmachine}]
			Een niet-deterministische Turingmachine $M$ bestaat uit een zestal $M = (Q,\Sigma,T,P,q_0,F)$ dat aan precies dezelfde voorwaarden voldoet als in \textbf{Theoretische Zever \ref{tm}}, behalve dat $P$ nu geen functie meer hoeft te zijn, maar slechts een relatie tussen $(Q\backslash F) \times \Sigma$ en $Q \times \Sigma \times {L, R, 0}$.
		\end{definition}
	\end{leftbar}
	\textbf{Praktisch}: een NDTM kan \textbf{meerdere acties} ondernemen voor eenzelfde toestand. 
		De NDTM behandelt elk van deze acties apart, maar in \textbf{parallel}. 
		Indien 1 van de gevolgde paden in een aanvaardbare eindtoestand stopt, dan \textbf{aanvaardt} de NDTM de input. 
		De \textbf{rekentijd} is gelijk aan het aantal stappen in het kortste dergelijke pad.
		De NDTM \textbf{beslist} een taal als die voor elke inputstring in \textbf{eindige tijd} beslist of de string in $L(M)$ zit of niet.
	\subsection{Analyse van algoritmen}
	Complexiteit van een \textbf{probleem} = complexiteit van het meest efficiënte \textbf{algoritme} dat het probleem oplost.
	\subsubsection{Tijdscomplexiteit}
	\textbf{Tijd} nodig om een probleem op te lossen hangt af van de grootte $n$ van de input.
	\begin{leftbar}
		\begin{definition}[\textit{Tijdscomplexiteit}]
			De \textbf{tijdscomplexiteit} van een bepaald algoritme $A$ is een functie $tijd_A(n) : \mathbb{N} \rightarrow\mathbb{N}$ die voor een gegeven invoeromvang $n$ het maximum \textbf{aantal elementaire bewerkingen} aangeeft, die door het algoritme $A$ bij een invoeromvang van grootte $n$ zullen worden uitgevoerd.
		\end{definition}
	\end{leftbar}
	$tijd_A(n)$ is worst-case maat.
	
	Niet geïnteresseerd in werkelijke (kwantitatieve) uitdrukking voor $tijd_A(n)$, wel kwalitatieve ($\mathcal{O}, \thicksim$).
	\subsubsection*{Big Oh ($\mathcal{O}$)}
	\begin{leftbar}
		\begin{definition}[\textit{$\mathcal{O}$-notatie}]
			Indien $f$ en $g$ functies zijn van $\mathbb{N}$ naar $\mathbb{R}^+$, dan zeggen we ``$f(n)$ is $\mathcal{O}(g(n))$'' of ``$f$ is $\mathcal{O}(g)$'' als
			\[ \exists c\in\mathbb{R}_0^+,\exists N\in\mathbb{N},\forall n\in\mathbb{N}:n\geq N\implies f(n)\leq cg(n) \] 
			Men zegt ook wel: $f$ is van orde $g$, of $f$ wordt asymptotisch gedomineerd door $g$.
		\end{definition}
	\end{leftbar}
	\begin{leftbar}
		\begin{definition}[\textit{Asymptotische equivalentie}]
			Twee functies $f,g : \mathbb{N} \rightarrow \mathbb{R}^+$ worden \textbf{asymptotisch equivalent} genoemd indien
			\begin{center}
				$f$ is $\mathcal{O}(g)$ en $g$ is $\mathcal{O}(f)$.
			\end{center}
			We noteren deze situatie door $f$ is $\Theta(g)$ (en dus ook $g$ is $\Theta(f)$).
		\end{definition}
	\end{leftbar}
	Algoritme $A$ is beter dan $B$ indien:
	\begin{itemize}
		\item $tijd_A(n)$ is $\mathcal{O}tijd_B(n))$, maar
		\item $tijd_B(n)$ is niet $\mathcal{O}tijd_A(n))$.
	\end{itemize}
	\subsubsection*{Tilde ($\thicksim$)}
	Wordt niet gebruikt in deze cursus, wegens te specifiek.
	\subsubsection*{Polynomiaal vs. exponentieel}
	\begin{leftbar}
		\begin{definition}[\textit{Polynomiale tijd}]
			We noemen een algoritme van polynomiale tijd als en slechts als zijn tijdscomplexiteit $\mathcal{O}(n^k)$ is voor een $k \in\mathbb{N}$.
		\end{definition}
	\end{leftbar}
	\begin{leftbar}
		\begin{definition}[\textit{Exponentiële tijd}]
			We noemen een algoritme van exponentiële tijd als en slechts als zijn tijdscomplexiteit $\mathcal{O}(\exp(n^k))$ is voor een $k \in\mathbb{N}$.
		\end{definition}
	\end{leftbar}
	\begin{remark}
		Exponentiële tijd is een bovengrens; algos van polynomiale tijd zijn een deelverzameling van die van exponentiële tijd.	
	\end{remark}
	\subsubsection*{Beheersbare en onbeheersbare problemen}
	TSP op p. 37, uitgebreider in sectie 3.5.
	\subsubsection{Bepalen van complexiteit in concrete voorbeelden}
	Enkele voorbeelden en 2 eigenschappen vanaf p. 39 in de cursus.
	\subsection{Complexiteitsklassen van beslissingsproblemen}
	Complexiteit van een probleem: gegeven een bepaald soort probleem van grootte $n$, hoeveel stappen heeft het \textbf{best mogelijke algoritme} (of TM) in het \textbf{slechtste geval} nodig om dit probleem op te lossen?
	\subsubsection{\boldmath$P$ en \boldmath$NP$}
	\begin{description}
		\item[\boldmath$P$:] \textbf{beslisbaar} in polynomiale (aantal stappen is $\mathcal{O}(n^k)$) tijd door een \textit{TM}. ($\rightarrow$ gemakkelijk, beheersbaar $\sim$ ``tractable'')
		\item[\boldmath$NP$:] \textbf{verifieerbaar} in polynomiale tijd door een \textit{TM}. $\sim$ `herkenbaar in polynomiale tijd door een \textit{NDTM}' ($\rightarrow$ moeilijke problemen, ``intractable'')
	\end{description}
	\begin{center}
		\boldmath$P$ $\subseteq$ \boldmath$NP$
	\end{center}
	\subsubsection{De klasse \boldmath$NP$-compleet (\boldmath$NPC$)}
	Een taal is niet moeilijker te beslissen dan een andere als er een \textbf{polynomiaal} algoritme bestaat om eender welk woord uit de eerste taal te \textbf{vertalen} in een woord uit de tweede.
	\begin{leftbar}
		\begin{definition}[\textit{$\propto$ = `polynomiaal transformeerbaar'}]
			$L_1 \propto L_2 \iff$
			\begin{itemize}
				\item $\exists f:T_1^* \rightarrow T_2^*: s \in L_1 \iff f(s) \in L_2, 2)$
				\item $f$ moet polynomiaal berekenbaar zijn
			\end{itemize}
		\end{definition}
	\end{leftbar}
	$\sim$ een probleem omzetten naar een ander probleem waarvoor reeds een efficient algoritme beschikbaar is.
	\begin{leftbar}
		\begin{definition}[\textit{$\propto$ is transitief}]
			$L_1 \propto L_2$ en $L_2 \propto L_3 \implies L_1 \propto L_3$
		\end{definition}
	\end{leftbar}
	\textbf{Bewijs}: Gezien in de les, zie cursus.
%	\begin{enumerate}
%		\item 
%			\begin{itemize}
%				\item $L_1 \propto L_2 \implies \exists f:\forall x\in T_1^*:(x\in L_1\iff f(x) \in L_2)$
%				\item $L_2 \propto L_3 \implies \exists g:T_2^*\rightarrow T_3^*:\forall y\in T_2^*:(y\in L_2\iff g(y) \in L_3)$
%			\end{itemize}
%		Conclusie: er bestaat een $h:T_1^*\rightarrow T_3^*:\forall x\in T_1^*:(x\in L_1 \iff h(x)\in L_3)$
%		\item
%			$h$ kan polynomiaal berekend worden.
%	\end{enumerate}
%	\hfill\ensuremath{\square}
	\begin{leftbar}
		\begin{definition}
			Als $L_1 \propto \L_2$ en $L_2\in P \implies L_1\in P$.
		\end{definition}
	\end{leftbar}
	\textbf{Bewijs}: Gezien in de les, zie cursus.
	\begin{leftbar}
		\begin{definition}[\textit{Polynomiale equivalentie van talen}]
			\hfill \\
			
			$L_1 \sim L_2 \iff L_1\propto L_2$ en $L_2\propto L_1$
		\end{definition}
		\begin{definition}
			De relatie $\sim$ is een equivalentierelatie.
		\end{definition}
	\end{leftbar}
	\textbf{Bewijs}:
	\begin{enumerate}
		\item reflexief: $L_1 \sim L_1$ (want $L_1\propto L_1$)
		\item symmetrie: $L_1\sim L_2 \iff L_2\sim L_1$
		\item transitief: volgt uit transitiviteit van $\propto$.
	\end{enumerate}
	\begin{leftbar}
		\begin{definition}[\textit{De klasse van \textbf{NP}-complete talen}]
			Een taal $L$ is \textbf{NP}-compleet $\iff$
			\begin{enumerate}
				\item $L\in$ \textbf{NP}
				\item $\forall L'\in$ \textbf{NP}$:L'\propto L$
			\end{enumerate}
		\end{definition}
	\end{leftbar}
	\begin{leftbar}
		\begin{definition}\hfill \\
			\begin{enumerate}
				\item \textbf{NPC} is een equivalentieklasse voor de relatie $\thicksim$ (polynomiale equivalentie).
				\item Indien \textbf{NPC} $\bigcap$ \textbf{P} $\neq \emptyset$ dan is \textbf{NP} $=$ \textbf{P}.
			\end{enumerate}
		\end{definition}
	\end{leftbar}
	\subsubsection*{Satisfiability Problem}
	\begin{leftbar}
		\begin{description}
			\item[Gegeven] een eindige verzameling $U$ van Booleaanse variabelen en een eindige verzameling $C$ van formules over $U$.
			\item[Gevraagd] Kan aan $C$ voldaan worden?
		\end{description}
		\begin{definition}[\textit{Stelling van Cook}]
			SAT is \textbf{NP}-compleet.
		\end{definition}
	\end{leftbar}
	TSP is ook \textbf{NP}-compleet.
	\begin{leftbar}
		\begin{definition}
			Gegeven twee talen $L_1$ en $L_2$.
			Als $L_1 \propto L_2$ en $L_1 \in $ \textbf{NPC}, dan is ook $L_2 \in $ \textbf{NPC}.
		\end{definition}
	\end{leftbar}
	\begin{remark}
		Bewijs wordt als oefening gelaten.	
	\end{remark}
	
	% Grafentheorie
	\pagebreak
	\section{Grafentheorie}
	\subsection{Inleiding}
	Enkele voorbeelden als intro op de relatie probleem - grafenvoorstelling.
	\subsection{Grafen}
	\subsubsection{Basisdefinities}
	\begin{remark}
		Een \textit{multiverzameling} gelijkt op een verzameling, met als enige verschil dat \textit{hetzelfde element meerdere keren kan voorkomen} in een multiverzameling. De \textit{volgorde} van elementen in een multiverzameling heeft geen belang.
	\end{remark}
	\begin{remark}
		Een \textit{multipaar} is een multiverzameling met 2 elementen.	Met $\mathcal{M}_2(V)$ bedoelen we de verzameling van alle multiparen die elementen uit $V$ bevatten.
	\end{remark}
	\begin{leftbar}
		\begin{definition}[\textit{Graaf}]
			Een \textbf{graaf} is een drietal $(V,E,\phi)$, met $V$ een verzameling waarvan de elementen \textbf{knopen} genoemd worden; $E$ een verzameling waarvan de elementen \textbf{bogen} genoemd worden; en $\phi: E \rightarrow \mathcal{M}_2(V)$ een functie die met elke boog twee knopen associeert.
		\end{definition}
	\end{leftbar}
	\begin{leftbar}
		\begin{definition}[\textit{Lus}]
			Een lus is een boog $e$ waarvoor geldt dat er een $v \in V$ bestaat zo dat $\phi(e) = (v, v)$. M.a.w. een lus is een boog die een knoop met zichzelf verbindt.
		\end{definition}
		\begin{definition}[\textit{Parallele bogen}]
			In een graaf $G(V,E,\phi)$ noemen we de bogen $e_1$ en $e_2$ parallelle bogen als en slechts als  $\phi(e_1) = \phi(e_2)$. M.a.w. twee bogen zijn parallel als en slechts als ze dezelfde knopen met elkaar verbinden.
		\end{definition}
		\begin{definition}[Enkelvoudige graaf]
			Een enkelvoudige graaf is een graaf die noch lussen, noch parallelle bogen bevat. M.a.w.: $G(V, E, \phi)$ is enkelvoudig als en slechts als
			\begin{enumerate}
				\item $\forall e \in E : \phi(e) = (v, w) \implies v \neq w$, en
				\item $8e1,e2 2E:e1 6=e2 ) (e1)6= (e2)$.
			\end{enumerate}
		\end{definition}
	\end{leftbar}
	\begin{leftbar}
		\begin{definition}[\textit{Graaf (vereenvoudigd)}]
			 Een graaf is een koppel $(V,E)$, met $V$ een verzameling knopen, en $E$ een multiverzameling van multiparen uit $V$.
		\end{definition}
	\end{leftbar}
	\begin{leftbar}
		\begin{definition}[\textit{Graad}]
			De graad van een knoop $v$, genoteerd $\sigma(v)$, is het aantal bogen dat op $v$ invalt. Een lus telt hierbij voor twee (omdat de lus twee keer op de knoop invalt).
		\end{definition}
		\begin{definition}
			Het aantal bogen in een graaf is steeds de helft van de som van de graden.
		\end{definition}
		\begin{definition}
			De som van de graden van alle knopen in een graaf is steeds even.
		\end{definition}
		\begin{definition}
			Het aantal knopen met oneven graad in een graaf is altijd even.
		\end{definition}
	\end{leftbar}
	\subsubsection{Paden}
	\begin{leftbar}
		\begin{definition}[\textit{Pad}]
			Een pad in een graaf $G(V,E)$ is een rij bogen van de vorm $(v_0, v_1), (v_1, v_2), ... , (v_{n-1}, v_n)$ waarbij $\forall i : (v_i, v_{i+1}) \in E$.
		\end{definition}
	\end{leftbar}
	\begin{description}
		\item[Lengte] Het aantal bogen in het pad noemen we de lengte van het pad.
		\item[Lege pad] Het pad van lengte 0.
	\end{description}
	\begin{leftbar}
		\begin{definition}[\textit{Enkelvoudig pad}]
			Een enkelvoudig pad is een pad $(v_0, v_1, ... , v_{n-1}, v_n)$ waarvan alle knopen verschillend zijn, d.w.z., $\forall i, j : i \neq j \implies v_i \neq vj$.
		\end{definition}
		\begin{definition}[\textit{Kring, enkelvoudige kring}]
			Een kring is een pad $((v_0, v_1), (v_1, v_2), ... , (v_{n-1}, v_n))$ waarin alle bogen verschillend zijn, en waarvoor $v_0 = v_n$. Een enkelvoudige kring is een kring waarin ook alle knopen verschillend zijn, afgezien van $v_0 = v_n$.
		\end{definition}
		\begin{definition}[\textit{Samenhangende grafen}]
			Een graaf is samenhangend als en slechts als tussen elke twee knopen van de graaf een pad bestaat.
		\end{definition}
		\begin{definition}[\textit{Hamiltoniaans pad, Hamiltoniaanse kring}]
			Zij gegeven een graaf $G$. Een Hamiltoniaans pad van $G$ is een pad waarin elke knoop van $G$ precies een keer voorkomt. Een Hamiltoniaanse kring van $G$ is een enkelvoudige kring waarin elke knoop van $G$ voorkomt.
		\end{definition}
	\end{leftbar}
	\begin{leftbar}
		\begin{definition}[\textit{Euleriaans pad, Euleriaanse kring}]
			Zij gegeven een graaf $G$. Een Euleriaans pad van $G$ is een pad waarin elke knoop van $G$ minstens 1 keer, en elke boog van $G$ precies een keer, voorkomt. Een Euleriaanse kring van $G$ is een Euleriaans pad dat ook een kring is.
		\end{definition}
		\begin{definition}
			Een graaf $G$ \textbf{heeft een Euleriaanse kring} als en slechts als de graaf \textbf{samenhangend} is en elke knoop een \textbf{even graad} heeft.
		\end{definition}
		\begin{definition}
			Een graaf $G$ \textbf{heeft een Euleriaans pad} als en slechts als de graaf \textbf{samenhangend} is en \textbf{hoogstens 2 knopen} een \textbf{oneven graad} hebben.
		\end{definition}
	\end{leftbar}
	\subsubsection{Deelgrafen en componenten}
	\begin{leftbar}
		\begin{definition}[\textit{Deelgraaf}]
			Een graaf $G'(V',E')$ is een deelgraaf van een graaf $G(V,E)$, genoteerd $G' \subseteq G$, als en slechts als $V' \subseteq V$ en $E' \subseteq E$.
		\end{definition}
		\begin{definition}[\textit{Geïnduceerde deelgraaf}]
			Gegeven een graaf $G(V,E)$ en een deelverzameling $V' \subseteq V$ noemen we $G'(V',E')$ de deelgraaf van $G$ geïnduceerd door $V'$ als en slechts als $E'=\{(v,w)\in E\ |\ v,w\in V'\}$
		\end{definition}
		\begin{definition}[\textit{Component}]
			Een graaf $G(V,E)$ is een component van een graaf $G'(V',E')$ als en slechts als $G\subseteq G'$, $G$ is niet leeg, $G$ is samenhangend, en er bestaat geen samenhangende graaf $G''$ waarvoor $G \subset G'' \subseteq G'$.
		\end{definition}
		\begin{remark}
			Zij $G(V,E)$ een graaf met $n$ componenten $G_i(V_i, E_i)$. Dan geldt: $\bigcup_iV_i=V, \bigcap_iV_i=\emptyset,\bigcup E_i=E$ en $\bigcap_iE_i=\emptyset$.
		\end{remark}
	\end{leftbar}
	\textbf{Bewijs}: Zie cursus.
	\subsubsection{Gerichte grafen}
	\begin{leftbar}
		\begin{definition}[\textit{Gerichte graaf}]
			Een gerichte graaf (di-graph) is een koppel $(V,E)$, met $V$ een verzameling waarvan de elementen knopen genoemd worden, en $E\subseteq V^2$ een verzameling koppels.
		\end{definition}
		\begin{definition}[\textit{Gericht pad, ongericht pad}]
			Een gericht pad in een gerichte graaf $G(V,E)$ is een pad $(v_0,v_1,...,v_n)$ met $\forall i:(v_i,v_{i+1})\in E \vee (v_{i+1},v_i) \in E$.
		\end{definition}
	\end{leftbar}	
	\subsection{Voorstellingen van grafen}
	\subsubsection{Buurmatrix}
	\begin{leftbar}
		\begin{definition}[\textit{Buurmatrix}]
			Gegeven een enkelvoudige graaf $G(V,E)$, met $V=\{v_1,V_2,...,v_n\}$, is de buurmatrix van $G$ (adjacency matrix) een $n\times n$-matrix $A$ met $A_{ij}=1\iff (v_i,v_j)\in E$, en $A_{ij}=0\iff (v_i,v_j)\notin E$.
		\end{definition}
		\begin{remark}
			De som van alle elementen op de $i$-de rij is gelijk aan de graad van $v_i$.	
		\end{remark}
		\begin{remark}
			Als $A$ de buurmatrix van een enkelvoudige graaf $G(V,E)$ is, geldt voor $A^k$ het volgende: voor alle $i$ en $j$ is $A_{ij}^k$ gelijk aan het aantal verschillende paden van lengte $k$ tussen $v_i$ en $v_j$.
		\end{remark}
	\end{leftbar}
	\textbf{Bewijs}: zie cursus p. 70.
	\subsubsection{Booleaanse buurmatrix}
	$\simeq$ buurmatrix, maar met booleaanse waarden. Som: disjunctie, product: conjunctie.
	\[ P = A\cdot B \iff \forall i,j: P_{ij} = \bigvee_k A_{ik} \wedge B_{kj} \]
	\[ S = A+B \iff \forall i,j: S_{ij} = A_{ij} \vee B_{ij} \]
	\begin{leftbar}
		\begin{definition}[\textit{Booleaanse buurmatrix}]
			Gegeven een enkelvoudige graaf $G(V,E)$, met $V = {v_1,v_2,...,v_n}$, is de booleaanse buurmatrix van $G$ een $n\times n$-matrix $B$ met $B_{ij} = ((v_i,v_j)\in E)$.
		\end{definition}
		Analoog met gewone buurmatrix:
		\begin{remark}
			Als $B$ de booleaanse buurmatrix van $G(V,E)$ is, geldt voor $B^k$ het volgende: voor alle $i$ en $j$ is $B_{ij}^k$ equivalent met ``er bestaat een pad van lengte $k$ van $v_i$ naar $v_j$''.	
		\end{remark}
		\begin{remark}
			Als $B$ de booleaanse buurmatrix van $G(V,E)$ is, geldt voor $S=\sum_{k=1}^l B^k$ het volgende: voor alle $i$ en $j$ is $S_{ij}$ equivalent met ``er bestaat een pad van lengte $l$ of korter	 tussen $v_i$ en $v_j$''.
		\end{remark}
	\end{leftbar}
	\subsubsection{Incidentiematrix}
	Rijen $\sim$ knopen, kolommen $\sim$ bogen; een 1 in een bepaalde cel betekent dat de bijhorende boog (kolom) invalt op de bijhorende knoop (rij).
	\begin{leftbar}
		\begin{definition}[\textit{Incidentiematrix}]
			Gegeven een enkelvoudige graaf $G(V,E)$, met $V=\{v_1,v_2,...,v_n\}$ en $E=\{e_1,e_2,...,e_m\}$, is de incidentiematrix van $G$ een $n\times n$-matrix $A$ met $A_{ij}=1$ als $e_j$ invalt op $v_i$, en $A_{ij}=0$ in alle andere gevallen.
		\end{definition}
	\end{leftbar}
	\subsection{Isomorfisme van grafen}
	Stellen dezelfde structuur voor.
	\begin{leftbar}
		\begin{definition}[\textit{Graaf-isomorfisme}]
			Twee grafen $G(V,E)$ en $G'(V',E')$ zijn isomorf als en slechts als er een bijectie $h:V\to V'$ bestaat, zodat $\{h(x)\ |\ x\in V\} = V'$ en $\{(h(x),h(y))\ |\ (x,y)\in E\}=E'$.
		\end{definition}
		\begin{remark}
			Twee enkelvoudige grafen zijn isomorf als en slechts als er een ordening van de knopen bestaat zodat hun buurmatrix gelijk is.	
		\end{remark}
	\end{leftbar}
	\textbf{Bewijs}: zie cursus.
	\begin{leftbar}
		\begin{remark}
			Twee grafen $G$ en $G'$ zijn isomorf als en slechts als er een ordening van de knopen en bogen bestaat waarvoor de incidentiematrices van $G$ en $G'$ gelijk zijn.	
		\end{remark}
	\end{leftbar}
	\subsection{Gewogen grafen}
	Kortste pad = pad met kleinste gewicht.
	\subsubsection{Dijkstra, versie 1: gewicht van kortste pad}
	\begin{algorithm}[H]
		$R:=\emptyset$\;
		$L(a):=0$\;
		$\forall v\neq a:L(v):=\infty$\;
		\While{$z\notin R$}{
			kies $v\in V\backslash R$ zo dat $L(v)$ zo klein mogelijk is\;
			$R:=R\cup\{v\}$\;
			\ForEach{boog $(v,v')\in E$ met $v'\in V\backslash R$}{
				$L(v'):=min\{L(v)+w(v,v'),L(v')\}$
			}
		}
		\caption{Dijkstra's kortste pad algoritme}
	\end{algorithm}
	\textbf{Bewijs}: correctheidsbewijs voor Dijkstra's algoritme, cursus p. 76.
	\subsubsection{Dijkstra, versie 2}
	\begin{algorithm}[H]
		$R:=\emptyset$\;
		$L(a):=0$\;
		$\forall v\neq a:L(v):=\infty$\;
		\While{$z\notin R$}{
			kies $v\in V\backslash R$ zo dat $L(v)$ zo klein mogelijk is\;
			$R:=R\cup\{v\}$\;
			\ForEach{boog $(v,v')\in E$}{
				\If{$L(v)+w(v,v')<L(v')$}{
					$L(v'):=L(v)+w(v,v')$\;
					$p(v'):=v$\;
				}
			}
		}
		\caption{Dijkstra's kortste pad algoritme, versie 2}
	\end{algorithm}
	\subsubsection{Complexiteit van Dijkstra's algoritme}
	\begin{itemize}
		\item Elke knoop wordt maximaal 1 keer gekozen $\implies$ buitenste lus maximaal $n=V.length$ keer uitgevoerd
		\item Keuze van $v$ door overlopen van alle elementen in $V\backslash R \implies$ maximaal $n$
		\item Lus over alle bogen $(v,v')$ wordt zo vaak uitgevoerd als er bogen invallen op $v \implies$ maximaal $n-1$ voor enkelvoudige graaf
	\end{itemize}
	$\implies \mathcal{O}(n^2)$
	\begin{itemize}
		\item Elke boog maximaal 1 keer gebruikt $\implies$ aantal wijzigingen van $L$-waarde maximaal $E.length$
		\item $v\in V\backslash R$ met minimale $L(v)$ te vinden in minder dan lineaire tijd (e.g.: $V\backslash R$ geordend volgens $L(v)$)
	\end{itemize}
	$\implies \mathcal{O}(|V|\log|V|+|E|)$
	\subsection{Bijzondere klassen van grafen}
	\begin{leftbar}
		\begin{definition}[\textit{Kliek}]
			Een enkelvoudige graaf waarin elke knoop rechtstreeks verbonden is met elke andere knoop.
		\end{definition}
		\begin{remark}
			De kliek met $n$ knopen wordt $K_n$ genoemd.	
		\end{remark}
		\begin{definition}[\textit{Tweeledige graaf}]
			Een enkelvoudige graaf $G(V,E)$ is tweeledig als en slechts als $V$ opgedeeld kan worden in twee deelverzamelingen $V_1$ en $V_2$, zodat er enkel bogen bestaan tussen $V_1$ en $V_2$, maar nooit binnen $V_1$ of $V_2$.
		\end{definition}
		\begin{remark}
			Een tweeledige graaf wordt volledig verbonden genoemd als elke knoop uit $V_1$ met elke knoop uit $V_2$ verbonden is.
		\end{remark}
		\begin{remark}
			De volledig verbonden tweeledige graaf met $m$ knopen in $V_1$ en $n$ knopen in $V_2$ wordt $K_{m,n}$ genoemd.	
		\end{remark}
	\end{leftbar}
	\subsection{Vlakke grafen}
	\begin{leftbar}
		\begin{definition}[\textit{Vlakke graaf}]
			Een vlakke graaf is een graaf die getekend kan worden zonder snijdende bogen.
		\end{definition}
		\begin{remark}
			Elke deelgraaf van een vlakke graaf is vlak.	
		\end{remark}
		\begin{remark}
			Elke kringvrije graaf is vlak en heeft 1 zijvlak (gebied volledig omringd door kring).
		\end{remark}
	\end{leftbar}
	\subsubsection{Formule van Euler}
	\begin{leftbar}
		\begin{remark}
			In een kringvrije graaf met minstens 1 boog bestaat er steeds een knoop met graad 1.
		\end{remark}
		\textbf{Bewijs}: zie cursus p. 82
		\begin{definition}[\textit{Formule van Euler}]
			Zij $G$ een samenhangende vlakke graaf met $v\geq 1$ knopen, $e$ bogen en $f$ zijvlakken. Dan geldt: $v-e+f=2$.
		\end{definition}
		\textbf{Bewijs}: zie cursus p. 82
	\end{leftbar}
	\subsubsection*{Veelvlakken}
	Lees cursus p. 83
	\subsubsection{Karakterisatie van vlakke grafen}
	\begin{leftbar}
		\begin{definition}[\textit{$\beta,B$}]
			Gegeven een vlakke graaf $G$, noteren we het aantal bogen waardoor een zijvlak $z$ begrensd wordt als $\beta(z)$. De som van $\beta(z)$ voor alle zijvlakken $z$ wordt $B$ genoemd: $B=\Sigma_{z\in Z}\beta(z)$, met $Z$ de verzameling zijvlakken van de graaf.
		\end{definition}
		\begin{remark}
			Voor elke vlakke graaf geldt: $B\leq 2e$.	
		\end{remark}
		\begin{remark}
			Voor elke enkelvoudige vlakke graaf met $f\geq 2$ geldt: $2e\geq 3f$, of nog, $f\leq \frac{2}{3}e$.	
		\end{remark}
		\begin{remark}
			$K_5$ en $K_{3,3}$ zijn niet vlak.	
		\end{remark}
		\textbf{Bewijs}: zie cursus p. 84
	\end{leftbar}
	\subsubsection*{Homeomorfisme}
	\begin{leftbar}
		\begin{definition}[\textit{Homeomorfisme}]
			Een graaf $G(V,E)$ is homeomorf met een graaf $G'(V',E')$ als en slechts als $G'$ uit $G$ bekomen kan worden door een of meer keren een knoop $v$ met graad 2 te kiezen, die samen met zijn invallende bogen $(v,w)$ en $(v,u)$ te verwijderen, en boog $(u,w)$ toe te voegen.
		\end{definition}
		\begin{remark}
			Als $G$ homeomorf is met $G'$, geldt: $G$ is vlak $\iff G'$ is vlak.	
		\end{remark}
	\end{leftbar}
	\subsubsection*{De stelling van Kuratowski}
	\begin{leftbar}
		\begin{definition}[\textit{Stelling van Kuratowski}]
			Een graaf is vlak als en slechts als de graaf geen deelgraaf bevat die homeomorf is met $K_5$ en $K_{3,3}$.
		\end{definition}
		\textbf{Bewijs}: zie cursus p. 85
	\end{leftbar}
	\subsubsection{Duale grafen}
	\begin{leftbar}
		\begin{definition}[\textit{Duale graaf}]
			Zij $G$ een graaf met $v$ knopen, $e$, $f$ zijvlakken. De duale graaf $G'$ heeft 1 knoop voor elk zijvlak van $G$, dus $v' = f$ knopen. Voor elke boog tussen de oorspronkelijke zijvlakken is er een boog tussen de overeenkomstige knopen in de duale graaf.
		\end{definition}
		\begin{remark}
			De duale graaf van een vlakke graaf is ook vlak.	
		\end{remark}
		\textbf{Bewijs}: alweer `zie cursus', p. 86 deze keer
	\end{leftbar}
	\subsection{Kleuringen van grafen}
	\begin{leftbar}
		\begin{definition}[\textit{Kleuring van een graaf}]
			Met een kleuring van een graaf $G(V,E)$ bedoelt men een toekenning van een kleur aan elke $v\in V$ zodanig dat de kleur van $v$ en $w$ verschilt indien $(v,w)\in E$. Een $n$-kleuring is een kleuring met $n$ of minder verschillende kleuren. Een minimale kleuring is een $n$-kleuring met minimale $n$.
		\end{definition}
		\begin{remark}
			Voor elke enkelvoudige vlakke graaf met $e\geq 2$ geldt: $e\leq 3v-6$	
		\end{remark}
		\begin{remark}
			In elke vlakke, enkelvoudige graaf bestaat er minstens 1 knoop, zeg $v$, zodanig dat $\delta(v)\leq 5$	
		\end{remark}
		\textbf{Bewijs}: cursus p. 88
		\begin{remark}
			Elke enkelvoudige, vlakke graaf $G(V,E)$ heeft een 5-kleuring.	
		\end{remark}
		\textbf{Bewijs}: cursus p. 88
	\end{leftbar}
	\subsection{Bomen}
	% Start hier
	\subsection{Gewortelde bomen}
	\subsection{Netwerkmodellen en Petri-netten}
	
	%Vastepuntstheorie
	\pagebreak
	\section{Vastepuntstheorie}
	
	% Oefenzittingen
%	\pagebreak
%	\section{Oefenzittingen}
%	\subsubsection{Talen en eindige automaten}
%	\textbf{1.1 Reguliere expressies en talen}
%	\begin{enumerate}
%		\item 
%			\begin{enumerate} % $\Sigma = \{ \}$, regex: $$
%				\item $\Sigma = \{0, 1, 2, ..., 9\}$, regex: $1CC|200$
%				\item $\Sigma = \{0, 1, 2, ..., 9\}$, regex: $PCCC^*$
%				\item $\Sigma = \{1, 2, 3, 5, 7, 9\}$, regex: $(2|3|5|7|11|13|17|19)$
%				\item $\Sigma = \{0, 1, 2, ..., 9\}$
%				\item $\Sigma = \{x\}$ (willekeurig symbool voor lege taal, symbool dat in alfabet voorkomt moet niet per se gebruikt worden)
%				\item $\Sigma = \{0, 1, 2, ..., 9\}$, regex: $(G,)^*G$
%				\item geen taal
%				\item geen taal
%				\item $\Sigma = \{0, 1, 2, ..., 9, /, -\}$, regex: $(-)?(0|PC^*)/PC$
%				\item geen taal
%				\item $V_1 = \Sigma = \{a, b, c, ..., z, A, B, C, ..., Z,\}\ \bigcup Leestekens$, regex: alle woorden uit woordenboek, gesplitst door `|'
%				\item $\Sigma = V_1 \bigcup Leestekens \bigcup \{0, 1, 2, ..., 9\}$, niet regulier: onmogelijk te controleren of alle geopende haakjes ook sluiten (oneindig geheugen nodig, oplossing: Turingmachine?)
%				\item $\Sigma = Java\ characters$, niet regulier: zie bovenstaand haakjes argument.
%				\item niet regulier
%				\item Wel een taal, definitie Kleene-sluiting: string blijft eindig. Niet regulier: $a^nb^n$
%				\item Is een reguliere taal.
%			\end{enumerate}
%		\item
%			\begin{enumerate}
%				\item $(a|b|c)^*bac(a|b|c)^*bac(a|b|c)^*$
%				\item $(a|b|c)^*(aaa|bbb|ccc)$
%				\item $(a|\lambda)(G(D|\lambda))^*$
%				\item $D = (b|c)^*, (DaDbDbD)|(DbDaDbD)|(DbDbDaD)$
%			\end{enumerate}
%		\item
%			Neen, exact evenveel: $aa^*=a+$, $(a|\lambda)=a?$
%	\end{enumerate}
%	\textbf{1.2 Eindige automaten en reguliere talen}
%	\begin{enumerate}
%		\item 
%			\begin{enumerate}
%				\item $(ab)^*$
%				\item $(b^*|(ab^*a))^*$
%				\item $k(a|o)t((m|p)(a|o)t)^*$
%			\end{enumerate}
%		\item
%			\begin{enumerate}
%				\item 
%					\[
%					\begin{tikzpicture}[shorten >=1pt,node distance=2cm,auto,font=\fontfamily{lmr}\selectfont]
%						\node[state,initial,accepting] (0)	 {$q_0$};
%						\node[state] (2) [below right of=0] {$q_2$};
%						\node[state] (1) [above right of=2] {$q_1$};
%						\node[state, dashed] (3) [above right of=1] {};
%						
%						\path[->]	(0) 	edge [bend right] node {b} (2)
%									(2) edge [bend right] node {l} (1)
%									(1) edge [bend right] node {a} (0);
%						\path[->, dashed]	(0) edge [bend left] node {l,a} (3)
%											(1) edge node {b,l} (3)
%											(2) edge [bend right] node [swap] {b,a} (3);
%					\end{tikzpicture}
%					\]
%			\end{enumerate}
%		\item
%			\begin{enumerate}
%				\item True, zie oef 1
%				\item False, alle getallen groter dan 1000
%				\item T, def. reguliere taal
%				\item T
%				\item F, pompstelling
%				\item F, lege verzameling
%				\item F, pompstelling
%			\end{enumerate}
%		\item
%			\begin{enumerate}
%				\item letterlijk definitie
%				\item automaat, string die eerst aanvaard wordt, wordt nu niet meer aanvaard en omgekeerd $\Rightarrow$ automaat $\Rightarrow$ reguliere taal
%				\item (\textit{Wetten van De Morgan}) $(L_1^C \bigcup L_2^C)^C \implies L_1 \in \mathcal{R} \iff \bar{L_1} \in \mathcal{R}$, analoog voor $L_2$
%			\end{enumerate}
%	\end{enumerate}
	
% Automaton with tikz
%
%	\begin{tikzpicture}[shorten >=1pt,node distance=2cm,auto,font=\fontfamily{lmr}\selectfont]
%		
%		\node[state,initial]		(q_0)						{$q_0$}; 
%		\node[state]				(q_1) [above right of=q_0] 	{$q_1$}; 
%		\node[state] 			(q_2) [below right of=q_0] 	{$q_2$}; 
%		\node[state,accepting]	(q_3) [below right of=q_1] 	{$q_3$};
%		
%		\path[->]	(q_0)  	edge  				node 		{0} (q_1)
%	          			   	edge  				node [swap]	{1} (q_2)
%	    			(q_1)  	edge  				node  		{1} (q_3)
%	          			 	edge [loop above] 	node 		{0} ()
%	    			(q_2) 	edge  				node [swap] 	{0} (q_3) 
%	          				edge [loop below] 	node 		{1} ();
%	\end{tikzpicture}	
	
\end{document}



















