\documentclass[a4paper]{article}

\usepackage[english]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{mathtools}
\usepackage{float}
\usepackage{enumerate}
\usepackage{hyperref}
\usepackage{comment}

\setlength{\parindent}{0pt}

\usepackage{amsthm}
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{corollary}{Corollary}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{claim}{Claim}[section]
\newtheorem{axiom}{Axiom}[section]

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]

\theoremstyle{remark}
\newtheorem{remark}{Remark}[section]
\newtheorem{example}{Example}[section]
\newtheorem{observation}{Observation}[section]

\let\originalleft\left
\let\originalright\right
\renewcommand{\left}{\mathopen{}\mathclose\bgroup\originalleft}
\renewcommand{\right}{\aftergroup\egroup\originalright}
\newcommand{\laplace}[1]{\mathcal{L}\left\{#1\right\}}
\newcommand{\pset}[1]{\mathcal{P}\left(#1\right)}
\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\L}{\mathcal{L}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\inprod}[1]{\left\langle#1\right\rangle}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\val}{val}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\charac}{char}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\intemb}{int}
\DeclareMathOperator{\com}{com}
\DeclareMathOperator{\vecspan}{span}
\DeclareMathOperator{\defequiv}{\mkern4mu :\mkern-8mu \iff}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\lcm}{lcm}

\newcommand{\ind}[1]{\mathbf{1}_{\left\{#1\right\}}}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\hateq}{\mathrel{\widehat{=}}}

\makeatletter
\newcommand{\axcirc}[1]{\mathbin{\mathpalette\make@circled#1}}
\newcommand{\make@circled}[2]{%
	\ooalign{$\m@th#1\largecirc{#1}$\cr\hidewidth$\m@th#1#2$\hidewidth\cr}%
}
\newcommand{\largecirc}[1]{%
	\vcenter{\hbox{\scalebox{1.5}{$\m@th#1\bigcirc$}}}%
}
\makeatother

\newcommand{\letprob}{Let $(S, \Sigma, P)$ be a probability space. {}}
\let\letprobalways\letprob

% (un)comment to remove useless fluff
\renewcommand{\letprob}{}

\let\tilde\widetilde
\let\hat\widehat

\title{Languages \& Machines}
\author{Koen Oostveen}

\begin{document}
	\begin{titlepage}
		\maketitle
		\tableofcontents
		\thispagestyle{empty}
	\end{titlepage}
	\section{Preliminaries}
	\begin{definition}
		An \textbf{alphabet} is any finite set $\Sigma$. We say that the \textbf{language generated} by $\Sigma$, $\Sigma^*$, is the set of all finite sequences in $\Sigma$, that is,
		\[ \Sigma^* := \{ (a_i)_{i=1}^n \mid n \in \N, a_i \in \Sigma \} \]
		Elements of $\Sigma^*$ are called \textbf{words}. The unique sequence with length $0$ in $\Sigma^*$ is called the \textbf{empty word}, denoted by $\lambda$.
	\end{definition}
	\begin{remark}
		Lots of peculiarities already. Let $a, b \in \Sigma^*$ be words. Then $ab$ is defined to be the \textbf{concatenation} of $a$ with $b$. More precisely, if $a = (a_i)_{i=1}^n$ and $b = (b_i)_{i=1}^m$, then $ab := (c_i)_{i=1}^{n+m}$ such that
		\[ c_i := \begin{cases*}
			a_i & if $i \leq n$ \\
			b_{i - n} & otherwise
		\end{cases*} \]
		We also identify letters $a \in \Sigma$ with the word $(a_i)_{i=1}^1$ such that $a_1 := a$.
	\end{remark}
	\begin{lemma}
		Concatenation is associative.
	\end{lemma}
	\begin{definition}
		Given an alphabet $\Sigma$, we say that a \textbf{language} is a subset $L \subseteq \Sigma^*$.
	\end{definition}
	\begin{theorem}
		Let $\Sigma$ be an alphabet. Then
		\begin{itemize}
			\item $\lambda \in \Sigma^*$
			\item If $a \in \Sigma$ and $w \in \Sigma^*$, then $aw \in \Sigma^*$
		\end{itemize}
		Moreover, if we axiomatically defined $\Sigma^*$ this way, this would be equivalent to our original definition of $\Sigma^*$.
	\end{theorem}
	\begin{proof}
		This is essentially equivalent to
		\[ \forall w : w \in \Sigma^* \iff w = \lambda \lor \exists a \in \Sigma, w' \in \Sigma^* : aw' = w \]
		which kind of pops out trivially.
	\end{proof}
	\begin{theorem}
		Let $u, v \in \Sigma^*$, then their concatenation satisfies
		\[ uv = \begin{cases*}
			v & if $u = \lambda$ \\
			a(wv) & if $u = aw$ for some $a \in \Sigma$, $w \in \Sigma^*$
		\end{cases*} \]
		Moreover, if we recursively defined $uv$ this way, this would be equivalent to our original definition of $uv$, and associativity therefore also holds.
	\end{theorem}
	\begin{definition}
		Let $u \in \Sigma^*$ be a word. We define $u^R$, called the \textbf{reverse word} of $u$, to be
		\[ u^R := \begin{cases*}
			\lambda & if $u = \lambda$ \\
			w^R a & if $u = aw$ for some $a \in \Sigma$, $w \in \Sigma^*$
		\end{cases*} \]
	\end{definition}
	\begin{lemma}
		Let $u, v \in \Sigma^*$ be words, then $(uv)^R = v^R u^R$.
	\end{lemma}
	\begin{proof}
		We do induction over $u$. If $u = \lambda$, then $(uv)^R = v^R = v^R \lambda^R$. Otherwise, if $u = aw$ for some $a \in \Sigma$, $w \in \Sigma^*$, we have
		\[ (uv)^R = (a(wv))^R = (wv)^R a = v^R w^R a = v^R (aw)^R = v^R u^R \]
	\end{proof}
	\begin{definition}
		Let $\Sigma$ be an alphabet. We define the \textbf{language of palidromes} to be
		\[ L := \{ w \in \Sigma^* \mid w = w^R \} \]
	\end{definition}
	\begin{definition}
		Let $u \in \Sigma^*$. Let $n \in \N$. Then we define
		\[ u^n := \begin{cases*}
			\lambda & if $n = 0$ \\
			uu^m & if $n = \operatorname{succ}(m)$
		\end{cases*} \]
	\end{definition}
	\begin{lemma}
		We have $u^m u^n = u^{m+n}$ and $(u^m)^n = m^{mn}$ for all $u \in \Sigma^*$ and $m, n \in \N$.
	\end{lemma}
	\begin{proof}
		We only prove the first property. We proceed by induction on $m$. If $m = 0$, then $u^m = \lambda$, so
		\[ u^m u^n = \lambda u^n = u^n = u^{0+n} = u^{m+n} \]
		Otherwise, if $m = \operatorname{succ}(k)$ for some $k \in \N$, then
		\[ u^m u^n = uu^k u^n = uu^{k+n} = u^{\operatorname{succ}(k+n)} = u^{m+n} \]
	\end{proof}
	\begin{definition}
		Let $w \in \Sigma^*$ be a word. We define the \textbf{length of} $w$ to be the quantity $|w| \in \N$ given by
		\[ |w| := \begin{cases*}
			0 & if $w = \lambda$ \\
			\operatorname{succ}(|v|) & if $w = av$ for some $a \in \Sigma$, $v \in \Sigma^*$
		\end{cases*} \]
	\end{definition}
	\begin{definition}
		Let $L_1, L_2 \subseteq \Sigma^*$ be languages. We define the following sets (that are also languages)
		\[ L_1^R := \{ w \in \Sigma^* \mid w^R \in L \} \]
		\[ L_1 L_2 := \{ w \in \Sigma^* \mid \exists w_1 \in L_1, w_2 \in L_2 : w_1 w_2 = w \} \]
	\end{definition}
	\begin{theorem}
		Let $L_1, L_2 \subseteq \Sigma^*$ be languages. Then
		\begin{itemize}
			\item $|L_1 L_2| \leq |L_1| |L_2|$
			\item $|L_1 \cup L_2| \leq |L_1| + |L_2|$
		\end{itemize}
	\end{theorem}
	\begin{definition}
		Let $L \subseteq \Sigma^*$ be a language. Let $n \in \N^*$. We define
		\[ L^n := \begin{cases*}
			\{ \lambda \} & if $n = 0$ \\
			LL^m & if $n = \operatorname{succ}(m)$ for some $m \in \N$
		\end{cases*} \]
	\end{definition}
	\begin{definition}[Kleene Star]
		Let $L \subseteq \Sigma^*$ be a language. We define the following set $L^*$, called the \textbf{Kleene Star of} $L$:
		\[ L^* := \bigcup \{ L^n \mid n \in \N \} \]
		and the \textbf{Kleene plus}, $L^+$, of $L$:
		\[ L^+ := \bigcup \{ L^n \mid n \in \N^* \} = LL^* \]
	\end{definition}
	\begin{lemma}
		Let $L$ be a language. Then
		\begin{itemize}
			\item $L^+ = LL^*$
			\item $L^* = L^+ \cup \{\lambda\}$
			\item From the above two it follows; if $\lambda \in L$ then $L^+ = L^*$.
		\end{itemize}
	\end{lemma}
	\begin{definition}
		A \textbf{regular expression} is a sentence comprised of parentheses (that match!), words, empty sets, unions, concatenations, and Kleene Stars. More precisely, $\varnothing$, $\lambda$ and all $a \in \Sigma$ are regular expressions. If $E_1, E_2$ are regular expressions, then
		\begin{itemize}
			\item $E_1 E_2$ is a regular expression,
			\item $E_1 \cup E_2$ is a regular expression,
			\item $E_1^*$ is a regular expression.
		\end{itemize}
		There exist no others. A bit of syntactic sugar:
		\[ E_1^+ := E_1 E_1^* \]
		which is consistent in the sense that
		\[ \L(E_1)^+ = \L(E_1) \L(E_1)^* = \L(E_1^+) \]
	\end{definition}
	\begin{definition}
		Let $E$ be a regular expression. The \textbf{language generated} by $E$, denoted by $\L(E)$, is given by
		\begin{itemize}
			\item If $E = \varnothing$, then $\L(E) := \varnothing$
			\item If $E = \lambda$, then $\L(E) := \{\lambda\}$
			\item If $E = a$ for $a \in \Sigma$ then $\L(E) := \{ a \}$
			\item If $E = E_1 E_2$ then $\L(E) = \L(E_1) \L(E_2)$
			\item If $E = E_1 \cup E_2$, then $\L(E) = \L(E_1) \cup \L(E_2)$
			\item If $E = \tilde E^*$, then $\L(E) = \L(\tilde E)^*$
		\end{itemize}
	\end{definition}
	\begin{definition}
		Let $L$ be a language. $L$ is called a \textbf{regular language} if there exists a regular expression $E$ such that $L = \L(E)$.
	\end{definition}
	\begin{example}
		Some examples of regular languages. If $\Sigma := \{ a, b, c\}$, we can define the language of all words beginning in $ab$ and ending with $ba$ by the set
		\[ L := \{ w \in \Sigma^* \mid \exists \tilde w \in \Sigma^* : w = abwba \} \cup \{ aba \} \]
		A regular expression for $L$ is
		\[ E := \left( ab (a \cup b \cup c)^+ ba \right) \cup (aba) \]
		such that $\L(E) = L$. Others are in the slides, I cba
	\end{example}
	
	\newpage
	\section{DFA's}
	\begin{definition}
		A \textbf{deterministic finite automaton}, or DFA for short, is a tuple $(Q, \Sigma, \delta, q_0, F)$, where
		\begin{itemize}
			\item $Q$ is a set of states (any finite set)
			\item $\Sigma$ is an alphabet
			\item $\delta : Q \times \Sigma \to Q$, called the \textbf{transition function}
			\item $q_0 \in Q$, called the \textbf{initial state}
			\item $F \subseteq Q$, called the \textbf{accepting states}. We call the set $Q \setminus F$ the set of \textbf{nonaccepting states}.
		\end{itemize}
	\end{definition}
	\begin{definition}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA. We say that a word $w \in \Sigma^*$ is \textbf{accepted} by $M$, if either
		\begin{itemize}
			\item $w = \lambda$ and $q_0 \in F$, or
			\item $w = av$ for $a \in \Sigma$, $v \in \Sigma^*$ such that the word $v$ is accepted by $(Q, \Sigma, \delta, \delta(q_0, a), F)$
		\end{itemize}
		We say that the \textbf{language generated by} $M$ or the \textbf{accepting language} of $M$, denoted by $\L(M)$, is the set
		\[ \L(M) := \{ w \in \Sigma^* \mid w \text{ is accepted by } M \} \]
	\end{definition}
	\begin{definition}
		A \textbf{configuration} of a DFA $(Q, \Sigma, \delta, q_0, F)$ is an element of $Q \times \Sigma^*$.
	\end{definition}
	\begin{definition}
		Let $\sim \, \subseteq S \times S$ be a binary relation on some set $S$. We define the \textbf{reflexive transitive closure}, $\sim^*$, by
		\[ \sim^* := \bigcap \{ \approx \, \subseteq S \times S \mid \, \sim \, \subseteq \, \approx \land \approx \text{is reflexive and transitive} \} \]
		i.e. the smallest reflexive-transitive relation that contains $\sim$.
	\end{definition}
	\begin{definition}
		For a DFA $M$, we define a relation $\vdash \, \subseteq (Q \times \Sigma^*)^2$ on all configurations of $M$ by
		\[ (q, w) \vdash (\tilde q, \tilde w) \defequiv \begin{cases*}
			\tilde q = q \land \tilde w = w & if $w = \lambda$ \\
			\tilde q = \delta(q, a) \land \tilde w = v & if $w = av$ for $a \in \Sigma$, $w \in \Sigma^*$
		\end{cases*}  \]
		Informally,
		\[ (q, aw) \vdash (\delta(q, a), w) \]
		We denote its reflexive-transitive closure by $\vdash^*$.
	\end{definition}
	\begin{definition}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA. We define the \textbf{extended transition function} of $M$, $\hat \delta : Q \times \Sigma^* \to Q$ by $(q, w) \mapsto \hat \delta(q, w)$ where
		\[ \hat \delta(q, w) := \begin{cases*}
			q & if $w = \lambda$ \\
			\hat \delta(\delta(q, a), v) & if $w = av$ for $a \in \Sigma$, $v \in \Sigma^*$
		\end{cases*} \]
	\end{definition}
	\begin{theorem}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA. Let $w \in \Sigma^*$ be a word. The following are equivalent:
		\begin{itemize}
			\item $w$ is accepted by $M$
			\item There exists a $q \in F$ such that $(q_0, w) \vdash^* (q, \lambda)$
			\item $\hat \delta(q_0, w) \in F$
		\end{itemize}
%		A word $w \in \Sigma^*$ is accepted by $M$ if and only if there exists a state $q \in F$ such that $(q_0, w) \vdash^* (q, \lambda)$.
	\end{theorem}
	\begin{definition}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA. We define the \textbf{complement} of $M$, denoted by $M'$, to be the DFA
		\[ M' := (Q, \Sigma, \delta, q_0, Q \setminus F) \]
	\end{definition}
	\begin{theorem}
		Let $M$ be a DFA, then $\L(M') = \Sigma^* \setminus \L(M) =: \overline{\L(M)}$.
	\end{theorem}
	\begin{proof}
		Let $w$ be a word.
		\begin{align*}
			w \in \L(M') &\iff \hat \delta(q_0, w) \in Q \setminus F \\
			&\iff \hat \delta(q_0, w) \notin F \\
			&\iff w \notin \L(M) \\
			&\iff w \in \Sigma^* \setminus \L(M)
		\end{align*}
%		Let $w \in \L(M')$, then $\hat \delta(q_0, w) \in Q \setminus F$
	\end{proof}
	
	\newpage
	\section{NFA's}
	\begin{definition}
		A \textbf{nondeterministic finite automaton}, or NFA for short, is a tuple $(Q, \Sigma, \delta, q_0, F)$, where
		\begin{itemize}
			\item $Q$ is a set of states (any finite set)
			\item $\Sigma$ is an alphabet
			\item $\delta : Q \times \Sigma \to \pset Q$, called the \textbf{transition function}
			\item $q_0 \in Q$, called the \textbf{initial state}
			\item $F \subseteq Q$, called the \textbf{accepting states}. We call the set $Q \setminus F$ the set of \textbf{nonaccepting states}.
		\end{itemize}
	\end{definition}
	\begin{remark}
		Note the definition of $\delta : Q \times \Sigma \to \pset Q$. Intuitively, this means that for any particular configuration, there may be $0$ or more legal next configurations. Note also that every DFA is an NFA (up to injection) but the reverse is not true. The injection (embedding that we use is): $(Q, \Sigma, \delta, q_0, F) \mapsto (Q, \Sigma, \delta', q_0, F)$ where $\delta' : Q \times \Sigma \to \pset Q$ is given by $(q, w) \mapsto \{ \delta(q, w) \}$. We need to redefine acceptance.
	\end{remark}
		\begin{definition}
			Let $M = (Q, \Sigma, \delta, q_0, F)$ be an NFA. We say that a word $w \in \Sigma^*$ is \textbf{accepted} by $M$, if either
			\begin{itemize}
				\item $w = \lambda$ and $q_0 \in F$, or
				\item $w = av$ for $a \in \Sigma$, $v \in \Sigma^*$, and there exists a $q \in \delta(q_0, a)$ such that the word $v$ is accepted by $(Q, \Sigma, \delta, q, F)$.
			\end{itemize}
		\end{definition}
		\begin{definition}
			For an NFA $M$, we define a relation $\vdash \, \subseteq (Q \times \Sigma^*)^2$ on all configurations of $M$ by
			\[ (q, aw) \vdash (\tilde q, w) \]
			if $\tilde q \in \delta(q, a)$.
		\end{definition}
		\begin{definition}
			Let $M = (Q, \Sigma, \delta, q_0, F)$ be an NFA. We define the \textbf{extended transition function} of $M$, $\hat \delta : Q \times \Sigma^* \to \pset{Q}$ by
			\[ \hat \delta(q, w) := \begin{cases*}
				\{q\} & if $w = \lambda$ \\
				\displaystyle \bigcup_{\tilde q \in \delta(q, a)} \hat \delta(\tilde q, v) & if $w = av$ for $a \in \Sigma$, $v \in \Sigma^*$
			\end{cases*} \]
		\end{definition}
		\begin{theorem}
			Let $M = (Q, \Sigma, \delta, q_0, F)$ be an NFA. Let $w \in \Sigma^*$ be a word. The following are equivalent:
			\begin{itemize}
				\item $w$ is accepted by $M$
				\item There exists a $q \in F$ such that $(q_0, w) \vdash^* (q, \lambda)$
				\item $\hat \delta(q_0, w) \cap F \neq \varnothing$
			\end{itemize}
		\end{theorem}
	\newpage
	\subsection{NFA with $\lambda$-steps}
	\begin{definition}
		A \textbf{nondeterministic finite automaton} with $\lambda$-steps, or NFA-$\lambda$ for short, is a tuple $(Q, \Sigma, \delta, q_0, F)$, where
		\begin{itemize}
			\item $Q$ is a set of states (any finite set)
			\item $\Sigma$ is an alphabet
			\item $\delta : Q \times (\Sigma \cup \{ \lambda \}) \to \pset Q$, called the \textbf{transition function}
			\item $q_0 \in Q$, called the \textbf{initial state}
			\item $F \subseteq Q$, called the \textbf{accepting states}. We call the set $Q \setminus F$ the set of \textbf{nonaccepting states}.
		\end{itemize}
	\end{definition}
	\begin{definition}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be an NFA-$\lambda$. We say that a word $w \in \Sigma^*$ is \textbf{accepted} by $M$, if either
		\begin{itemize}
			\item $w = \lambda$ and $q_0 \in F$, or
			\item $w$ is accepted by $(Q, \Sigma, \delta, \delta(q_0, \lambda), F)$, or
			\item $w = av$ for $a \in \Sigma$, $v \in \Sigma^*$, and there exists a $q \in \delta(q_0, a)$ such that the word $v$ is accepted by $(Q, \Sigma, \delta, q, F)$.
		\end{itemize}
	\end{definition}
	\begin{definition}
		For an NFA-$\lambda$ $M$, we define a relation $\vdash \, \subseteq (Q \times \Sigma^*)^2$ on all configurations of $M$ by
		\[ (q, aw) \vdash (\tilde q, w) \]
		if $\tilde q \in \delta(q, a)$, or $(q, w) \vdash (\tilde q, w)$ if $\tilde q \in \delta(q, \lambda)$.
	\end{definition}
	\begin{remark}
		We skip the definition of the extended transition function, we first need another concept.
	\end{remark}
	\subsubsection{$\lambda$-closure}
	\begin{definition}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be an NFA-$\lambda$. Let $P \subseteq Q$ be a set of states. We say that $P$ is $\lambda$-\textbf{closed} if for all $q_1 \in P$, if $q_2 \in \delta(q_1, \lambda)$ then also $q_2 \in P$..
	\end{definition}
	\begin{definition}
		Let $M$ be an NFA-$\lambda$ as before. Let $q \in Q$. We define the $\lambda$-\textbf{closure of} $q$ to be the set $\Lambda(q)$ given by
		\[ \Lambda(q) := \bigcap \{ P \subseteq Q \mid q \in P \land P \text{ is } \lambda\text{-closed} \} \]
		In other words, $\Lambda(q)$ is the smallest $\lambda$-closed subset of $Q$ that contains $q$. Intuitively, this is the set of states reachable from $q$ by taking only $\lambda$-steps.
	\end{definition}
	\begin{definition}
		Let $P \subseteq Q$. We define the $\lambda$-closure of $P$ to be the union of the $\lambda$-closures of all elements of $P$, that is
		\[ \Lambda(P) := \bigcup \{ \Lambda(q) \mid q \in P \} \]
		Intuitively, this is the set of states reachable by starting at any state in $P$ and then taking only $\lambda$-steps.
	\end{definition}
	\subsubsection{Extended transition function}
	\begin{definition}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be an NFA. We define the \textbf{extended transition function} of $M$, $\hat \delta : Q \times \Sigma^* \to \pset{Q}$ by
		\[ \hat \delta(q, w) := \begin{cases*}
			\Lambda(q) & if $w = \lambda$ \\
			\displaystyle \bigcup_{\tilde q \in \delta(q, \lambda)} \Lambda(\hat \delta(\tilde q, av)) \cup \bigcup_{\tilde q \in \delta(q, a)} \Lambda(\hat \delta(\tilde q, v)) & if $w = av$ for $a \in \Sigma$, $v \in \Sigma^*$
%			\displaystyle \hat \delta(\delta(q, \lambda), w) \cup \bigcup_{\tilde q \in \delta(q, a)} \hat \delta(\tilde q, v) & if $w = av$ for $a \in \Sigma$, $v \in \Sigma^*$
		\end{cases*} \]
		Much simpler is:
		\[ \hat \delta(q, w) := \begin{cases*}
			\Lambda(q) & if $w = \lambda$ \\
			\displaystyle \bigcup_{\tilde q \in \hat \delta(q, v)} \Lambda(\delta(\tilde q, a)) & if $w = va$ for $a \in \Sigma$, $v \in \Sigma^*$
			%			\displaystyle \hat \delta(\delta(q, \lambda), w) \cup \bigcup_{\tilde q \in \delta(q, a)} \hat \delta(\tilde q, v) & if $w = av$ for $a \in \Sigma$, $v \in \Sigma^*$
		\end{cases*} \]
	\end{definition}
	\begin{theorem}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be an NFA-$\lambda$. Let $w \in \Sigma^*$ be a word. The following are equivalent:
		\begin{itemize}
			\item $w$ is accepted by $M$
			\item There exists a $q \in F$ such that $(q_0, w) \vdash^* (q, \lambda)$
			\item $\hat \delta(q_0, w) \cap F \neq \varnothing$
		\end{itemize}
	\end{theorem}
	\subsubsection{NFA to DFA}
	\begin{definition}
		Let $P \subseteq Q$, let $a \in \Sigma$. We define the $\lambda$-\textbf{transition} of $P$ when \textbf{taking} $a$, to be the set $\Delta(P, a)$, defined by
		\[ \Delta(P, a) := \bigcup \{ \Lambda(\delta(q, a)) \mid q \in \Lambda(P) \} \]
		which makes $\Delta : \pset Q \times \Sigma \to \pset Q$ .
		Using this, we can eliminate the $\lambda$-steps by defining the transition function $t : Q \times \Sigma \to \pset Q$ by
		\[ (q, a) \mapsto \Delta(\{q\}, a) \]
		which yields an NFA (\textbf{without} $\lambda$-steps) $(Q, \Sigma, t, q_0, F)$.
	\end{definition}
	\begin{lemma}
		Let $P \subseteq Q$, $a \in \Sigma$,
		\[ \Delta(P, a) = \bigcup \{ \Delta(\{q\}, a) \mid q \in P \} = \bigcup \{ t(q, a) \mid q \in P \} \]
	\end{lemma}
	\begin{theorem}
		NFA's, with or without $\lambda$-steps, are equivalent to DFA's.
	\end{theorem}
	\begin{proof}
		We saw that DFA's can be embedded into NFA's. NFA's also can be embedded into NFA-$\lambda$'s, let $(Q, \Sigma, \delta, q_0, F)$ be an NFA, define the transition function $\delta' : Q \times (\Sigma \cup \{ \lambda \}) \to \pset Q$ through
		\[ (q, a) \mapsto \begin{cases*}
			\varnothing & if $a = \lambda$ \\ 
			\delta(q, a) & otherwise
		\end{cases*} \]
		Then $(Q, \Sigma, \delta', q_0, F)$ is an NFA-$\lambda$ with the same accepted language.\\
		Now let $(Q, \Sigma, \delta, q_0, F)$ be an NFA-$\lambda$. Then $(\pset Q, \Sigma, \Delta, \Lambda(q_0), F')$ with
		\[ F' := \{ X \in \pset Q \mid X \cap F \neq \varnothing \} \]
		is a DFA that accepts the same language.
	\end{proof}
	\begin{remark}
		Note that without $\lambda$-steps, it holds that for all $P \subseteq Q$, we have $\Lambda(P) = P$, so that
		\[ \Delta(P, a) = \bigcup \{ \delta(q, a) \mid q \in P \} \]
		which makes the equivalence even more apparent.
	\end{remark}
	\begin{remark}
		Note that most states in $\pset Q$ might not be reachable: consider the case where we turned a DFA with states $Q$ into an NFA-$\lambda$, and then back, which gets states $\pset Q$. Note that $|\pset Q| = 2^{|Q|}$, and of course if $Q \neq \varnothing$ then $|\pset Q| > |Q|$, even though they accept the same language in the same kind of way.\\
		So the following genius algorithm to construct a DFA from an NFA-$\lambda$ exists that `filters out' the unneccesary state: use a graph-search algorithm to visit every state in $\pset Q$ by applying every possible symbol in $\Sigma$ to any already visited state $P \in \pset Q$, where you start with $\Lambda(q_0)$. Say this produces states $Q' \subseteq \pset Q$, then the transition function is just $\Delta$ restricted to $Q'$ in the domain and codomain.
	\end{remark}
	\subsubsection{RE to NFA}
	\begin{definition}
		An NFA-$\lambda$ $M = (Q, \Sigma, \delta, q_0, F)$ is called \textbf{composable} if
		\begin{itemize}
			\item There does not exist $q \in Q$ and $a \in \Sigma$ such that $q_0 \in \delta(q, a)$, and
			\item $F = \{q_f\}$ is a singleton set, and
			\item For all $a \in \Sigma$, $\delta(q_f, a) = \varnothing$.
		\end{itemize}
	\end{definition}
	\begin{definition}
		Let $M = (Q_M, \Sigma, \delta_M, m_0, \{m_f\})$ and $N = (Q_N, \Sigma, \delta_N, n_0, \{n_f\})$ be composable NFA-$\lambda$'s. We define the \textbf{composition} of $M$ with $N$, denoted $M \circ N$, to be the NFA-$\lambda$
		\[ M \circ N := \left( Q_M \sqcup Q_N, \Sigma, \delta_{M \circ N}, m_0, \{n_f\} \right) \]
		where $\delta_{M \circ N} : (Q_M \sqcup Q_N) \times (\Sigma \cup \{ \lambda \}) \to \pset (Q_M \sqcup Q_N)$ is given by
		\[ \delta_{M \circ N}(q, a) := \begin{cases*}
			n_0 & if $q = m_f$ and $a = \lambda$ \\
			\varnothing & if $q = m_f$ and $a \neq \lambda$ \\
			\delta_M(q, a) & if $q \in Q_M$ \\
			\delta_N(q, a) & if $q \in Q_N$
		\end{cases*} \]
%		TODO REVERSE THE DEFINITION, THIS LOOKS LIKE FUNCTION COMPOSITION, BUT WE WANT TO REVERSE THE READING ORDER.
	\end{definition}
	\begin{lemma}
		The composition of composable NFA-$\lambda$'s is composable.
	\end{lemma}
	\begin{proof}
		We go by each property. 
		\begin{itemize}
			\item If $n_0 \in \delta(q, a)$ for some $q, a$, in perticular because $n_0 \in Q_N$ we have that $n_0 \in \delta_N(q, a)$, which is a contradiction.
			\item $\{m_f\}$ is clearly a singleton.
			\item Let $a \in \Sigma$. Then $\delta(m_f, a) = \delta_M(m_f, a) = \varnothing$. \qedhere
		\end{itemize}
	\end{proof}
	\begin{theorem}
		Let $E$ be a regular expression over an alphabet $\Sigma$. Then there exists a (composable) NFA-$\lambda$ that accepts the same language.
	\end{theorem}
	\begin{proof}
		We proceed by induction on $E$. The base cases are:
		\begin{itemize}
			\item If $E = \varnothing$, $\L(E) = \varnothing$, and for $M = (\{q_0, q_1\}, \Sigma, \delta, q_0, \{q_1\})$ with $\delta(q, a) := \varnothing$ gives $\L(M) = \varnothing$.
			\item If $E = \lambda$, then $\L(E) = \{\lambda\}$, and for $M = (\{q_0, q_1\}, \Sigma, \delta, q_0, \{q_1\})$ with
			\[ \delta(q, a) := \begin{cases*}
				\{q_1\} & if $q = q_0$ and $a = \lambda$ \\
				\varnothing & otherwise
			\end{cases*} \]
			gives $\L(M) = \{\lambda\}$, note that $M$ is composable.
			\item If $E = b$ for some $b \in \Sigma$, then $\L(E) = \{b\}$, and for $M = (\{q_0, q_1\}, \Sigma, \delta, q_0, \{q_1\})$ with
			\[ \delta(q, a) := \begin{cases*}
				\{q_1\} & if $q = q_0$ and $a = b$ \\
				\varnothing & otherwise
			\end{cases*} \]
			gives $\L(M) = \{b\}$, note that $M$ is composable.
		\end{itemize}
		Suppose that we have composable $M_1, M_2$ for $E_1, E_2$ such that $\L(E_1) = \L(M_1)$ and $\L(E_2) = \L(M_2)$, we show that we can construct composable NFA-$\lambda$'s for $E_1 E_2$, $E_1 \cup E_2$ and $E_1^*$. Note that $\L(M_1 \circ M_2) = \L(M_1) \L(M_2) = \L(E_1) \L(E_2) = \L(E_1 E_2)$. We can do very similar things for $E_1 \cup E_2$ and $E_1^*$, but this is a lot of effort and can most easily be summarized in a diagram.
	\end{proof}
	
	\subsection{NFA to RE}
	\begin{definition}
		An \textbf{expression graph} is an NFA-$\lambda$, where the labels are replaced with regular expressions. We get rid of the transition function $\delta$ and instead specify just the inferences. Given a current state $q \in Q$ and a word $w \in \Sigma^*$, we define $(q, w) \vdash (\tilde q, \tilde w)$ if there exists a regular expression $E$ on the edge from $q$ to $\tilde q$ such that there exists a word $v$ such that $w = v\tilde w$ and $v$ is accepted by $E$.\\
		More formally, an expression graph is a tuple $(Q, \Sigma, E, L, q_0, F)$ such that
		\begin{itemize}
			\item $Q$ is any finite set of states
			\item $\Sigma$ is any alphabet
			\item $(Q, E)$ is a directed graph
			\item $L$ is a function from $E$ to regular expressions in $\Sigma$
			\item $q_0 \in Q$ is the initial state
			\item $F \subseteq Q$ is a set of accepting states
		\end{itemize}
		for which the relation $\vdash$ is given by: $(q, ab) \vdash (\tilde q, b)$ if $L(q, \tilde q)$ accepts $a$.
	\end{definition}
	\begin{remark}
		Because the `edges' of an NFA-$\lambda$ are characters in $\Sigma$ or $\lambda$, it is trivially an expression graph, by inclusion of characters and $\lambda$ into the regular expressions. The only issue is when there are multiple `edges' with different symbols on them, this can be resolved by merging them together and creating a `$\cup$' type regex.\\
		The bigger picture idea is now to take this expression graph and simplify it until there are only various edges remaining and the resulting regex can be readily read off.
	\end{remark}
	\begin{theorem}
		Let $(Q, \Sigma, E, L, q_0, F)$ be an expression graph. Let $q_1, q_2, q_3 \in Q$ be states such that there exists an edge $(q_1, q_2)$ and an edge $(q_2, q_3)$ in $E$, as well as $q_1 \neq q_2$ and $q_2 \neq q_3$, but possibly $q_1 = q_3$. Then by deleting $q_2$ and creating an edge $(q_1, q_3)$ with the expression
		\[ \begin{cases*}
			L(q_1, q_2) L(q_2, q_3) & if $(q_2, q_2) \notin E$ \\
			L(q_1, q_2) L(q_2, q_2)^* L(q_2, q_3) & if $(q_2, q_2) \in E$
		\end{cases*} \]
		for every possible combination of $q_1, q_2, q_3$ like the above, yields an expression graph that accepts the same language.
	\end{theorem}
	
	\subsection{Overarching conclusion}
	We have shown that NFA-$\lambda$'s and DFA's are equivalent, as well as NFA-$\lambda$'s being equivalent to regular expressions, so the class of languages definable through regexes, DFA's and NFA's are all the same: the class of regular languages.
	
	\section{Pumping lemma}
	Recall the Pigeonhole principle.
	\begin{theorem}
		Let $A$ and $B$ be finite sets. If $|A| > |B|$, then there does not exist an injection $f : A \to B$. That is, for every $f : A \to B$, there exists $x, y \in A$ such that $f(x) = f(y)$ but $x \neq y$.
	\end{theorem}
	Now suppose you have a DFA $M = (Q, \Sigma, \delta, q_0, F)$ that accepts a word $w$ with $|w| \geq |Q|$. Note that then, the function $f : \{0, \ldots, |w|\} \to Q$ mapping a character index in $w$ to the state the DFA is in after consuming the character at that index, with $f(0) := q_0$. Then $|\{0, \ldots, w\}| = |w| + 1 \geq |Q| + 1 > |Q|$, hence $f$ cannot be an injection, hence there must exist a state $q \in Q$ that is visited twice. From this we obtain the pumping lemma.
	\begin{lemma}
		Let $L$ be a regular language. Then there exists a $k > 0$ such that for all words $z \in L$ with $|w| \geq k$, we can write $z = uvw$ with $|uv| \leq k$, $v \neq \lambda$, and for all $i \in \N$, $uv^iw \in L$.
%		Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA.
	\end{lemma}
	\begin{proof}
		Let $L$ be a regular language, let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA that generates it, i.e. $\L(M) = L$, which exists by equivalence of DFA languages and regular languages. Let $k := |Q|$, let $z \in L$ be such that $|z| \geq k$. By the previous argument this gives us a state $q \in Q$ that is visited twice while accepting $z$. Let $z = z_1 \cdot \ldots \cdot z_n$, $z_1, \ldots, z_n \in \Sigma$. Suppose that state $q$ occurs at indices $i, j \in \N$ of $z$, wlog suppose $i < j$. Let $u := w_1 \cdot \ldots \cdot w_i$, let $v := w_{i+1} \cdot \ldots \cdot w_{j}$, let $w := w_{j+1} \cdot \ldots \cdot w_n$, then clearly $z = uvw$. Also, because $i+1 \leq j$, we have $v \neq \lambda$. Note that $|uv| \leq k$ would follow if $j \leq k$, which it wlog could by only considering those indices of $z$, the pigeonhole principle still holds. Note that by construction,
		\begin{align*}
			\hat \delta(q_0, u) = q, && \hat \delta(q, v) = q, && \hat \delta(q, w) \in F
		\end{align*}
		Now by doing a hidden induction, $\hat \delta(q, v^i) = q$ pops right out, whence $\hat \delta(q_0, uv^iw) \in F$ for all $i$, so $uv^iw \in F$.
	\end{proof}
	\begin{corollary}
		Any regular language $L$ generated by a DFA that accepts a word with length at least the amount of states it has, is infinite. 
	\end{corollary}
	\newpage
	\section{DFA minimization}
	\begin{definition}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA. We say that two states $q_1, q_2 \in Q$ are \textbf{equivalent} if they accept the same language, that is,
		\[ \L(Q, \Sigma, \delta, q_1, F) = \L(Q, \Sigma, \delta, q_2, F) \]
	\end{definition}
	\begin{definition}
		A DFA $(Q, \Sigma, \delta, q_0, F)$ is called \textbf{minimal} if
		\begin{itemize}
			\item every state has a word that produces is, that is, for every $q \in Q$ there exists a $w \in \Sigma^*$ such that $\hat \delta(q_0, w) = q$, and
			\item for any two states $q_1, q_2 \in Q$, if they are equivalent, then $q_1 = q_2$.
		\end{itemize}
	\end{definition}
	\begin{definition}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA. A binary relation $D$ on $Q$ is called \textbf{distinguishing} if for all $x, y \in Q$ and $a \in \Sigma$ we have
		\begin{itemize}
			\item If $x \in F \iff y \notin F$ then $xDy$,
			\item If $\delta(x, a) D \delta(y, a)$ then $xDy$
		\end{itemize}
		The \textbf{distinguishability relation} is the intersection (the smallest) of the distinguishing relations on $M$.
	\end{definition}
	\begin{lemma}
		The negation of the distinguishability relation determines equivalence of states, which makes it an equivalence relation.
	\end{lemma}
%	\begin{proof}
%		Because the relation for which $xDy$ is defined to be false if neither of the above criteria is met, is also a distinguishing relation, we can assume that if $xDy$, then $x \in F \iff y \notin F$ or $\delta(x, a) D \delta(y, a)$ for some $a \in \Sigma$. Suppose two states $x, y$ are equivalent. By cases, suppose $x \in F$, then 
%		We just have to prove symmetry and transitivity. Suppose $xDy$. We may assumuse that either $x \in F \iff y \notin F$ or there exists an $a$ such that $\delta(x, a) D \delta(y, a)$, because the relation where otherwise, $xDy$ is taken to be false, is also a distinguishing relation. In both cases, symmetry is clear. Suppose also $yDz$, and we make a similar argument as before.
%	\end{proof}
	\begin{theorem}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA such that every state is reachable. Let $D \subseteq Q \times Q$ be the distinguishability relation on $M$. Let $\neg D$ be its negation, i.e. $x (\neg D) y \defequiv \neg xDy$. Then the DFA
		\[ M' := (Q/\neg D, \Sigma, \delta', [q_0]_{\neg D}, F') \]
		where $\delta' : Q/\neg D \times \Sigma \to Q/\neg D$ is (well-)defined by
		\[ ([q], a) \mapsto [\delta(q, a)] \]
		and
		\[ F' := \{ [q] \in Q/\neg D \mid q \in F \} \]
		makes $M'$ a minimal equivalent DFA of $M$.
	\end{theorem}
	\begin{proof}
		There are some comments below here that attempt to prove this.
%		We first show well-definition of $\delta'$. Suppose $q_1, q_2 \in Q$ are equivalent states. Let $a \in A$. It suffices to show that then $\delta(q_1, a)$ and $\delta(q_2, a)$ are equivalent. We have already argued this before, through the distinguishing relation. Namely, $x (\neg D) y$ implies that for all $a \in \Sigma$, $\delta(x, a) (\neg D) \delta(y, a)$.\\
%		It is easy to show that all states are still reachable, just take any word that would reach a certain $q \in Q$ in $M$, then the same word is reached in $M'$ by $[q]$.\\
%		Now, suppose that $[q_1], [q_2] \in Q/\neg D$ are equivalent. We show that this implies $q_1 (\neg D) q_2$. By contradiction, suppose $q_1$ and $q_2$ can be distinguished in $M$ but $[q_1], [q_2]$ cannot in $M'$. Let $w \in \Sigma^*$ be a word that distinguishes $q_1$ and $q_2$, i.e.
%		\[ \hat \delta(q_1, w) \in F \iff \hat \delta(q_2, w) \notin F \]
		
%		Note that if a state $q \in Q$ is accepting, then $[q] \in Q/\neg D$ is as well, so we must have some $a \in \Sigma$ such that $\delta(q_1, a) D \delta(q_2, a)$, whereas for this $a$ as well we have
%		\[ \delta'([q_1], a)(\neg D)\delta'([q_2], a) \iff [\delta(q_1, a)](\neg D)[\delta(q_2, a)] \]
	\end{proof}
%	\begin{remark}
%		The way we now make an algorithm to compute such a minimal DFA, is by finding these equivalence classes. We compute the $D$ relation iteratively, by starting by partitioning the states into whether they are accepting or not: we compute an array $D[i, j]$ with $1 \leq i < j \leq n$, which are indices in the set of states $Q = \{ q_1, \ldots, q_n \}$. For all $i, j$ such that $q_i \in F$ but $q_j \notin F$, set $D[i, j] := T$. Then, find all predecessors of any pair of distinguishable states with the same transition label (that is, find $k, l$ and $a \in \Sigma$ such that $\delta(q_k, a) = q_i$ and $\delta(q_l, a) = q_j$), and then also mark those as distinguishable. Continue this until nothing changes.\\
%		We can make this more efficient by not considering all pairs in $D$ every single iteration, instead we can store `dependencies' in another table $S[i, j]$ which contains sets of pairs of indices that depend on the distinguishability of $q_i, q_j$. Those `dependencies' are determined as follows: say we are looking at a pair $q_i, q_j$. We consider also every symbol $a \in \Sigma$. We then need to know whether $\delta(q_i, a) =: q_k$ and $\delta(q_j, a) =: q_l$ can be distinguished to determine the distinguishability of $q_i, q_j$. If we have computed this already, great, use that. If not, store $S[\min\{k, l\}, \max\{k, l\}] := S[\min\{k, l\}, \max\{k, l\}] \cup \{(i, j)\}$. Then, once we determine the distinguishability of a certain pair, immediately also reconsider all entries in $S$.  
%	\end{remark}
	\begin{definition}
		Let $M = (Q_M, \Sigma, \delta_M, m_0, F_M)$ and $N = (Q_N, \Sigma, \delta_N, n_0, F_N)$ be DFA's. A function
		\[ f : Q_M \to Q_N \]
		is called a \textbf{DFA isomorphism} from $M$ to $N$ if
		\begin{itemize}
			\item $f$ is invertible,
			\item for all $q \in Q_M$ and $a \in \Sigma$, we have $f(\delta_M(q, a)) = \delta_N(f(q), a)$,
			\item $F_N = f(F_M)$,
			\item $n_0 = f(m_0)$.
		\end{itemize}
		If such an $f$ exists, we say that $M$ and $N$ are \textbf{isomorphic} or \textbf{equal up to isomorphism}.
	\end{definition}
	\begin{theorem}
		For every DFA $M$, a unique (up to isomorphism) DFA $M'$ exists that accepts the same language, i.e. $\L(M) = \L(M')$.
	\end{theorem}
	\newpage
	\section{Composition of automata}
	\begin{definition}
		Let $M_1$ and $M_2$ be DFA/NFA/NFA-$\lambda$'s. We say that a DFA/NFA/NFA-$\lambda$ $M_1 \times M_2$ is the \textbf{product} of $M_1$ and $M_2$ if
		\[ \L(M_1 \times M_2) = \L(M_1) \cap \L(M_2) \]
	\end{definition}
	\begin{lemma}
		Let $M = (Q_M, \Sigma, \delta_M, m_0, F_M)$ and $N = (Q_N, \Sigma, \delta_N, n_0, F_N)$ be DFA's. A unique (up to isomorphism) product of $M$ and $N$ is given by
		\[ M \times N := (Q_M \times Q_N, \Sigma, \delta, (m_0, n_0), F_M \times F_N) \]
		where $\Sigma := \Sigma_M \cap \Sigma_N$,
		\[ \delta : (Q_M \times Q_N) \times \Sigma \to Q_M \times Q_N \]
		is given by
		\[ ((q_m, q_n), a) \mapsto (\delta_M(q_m, a), \delta_N(q_n, a)) \]
	\end{lemma}
	\begin{lemma}
		Let $M = (Q_M, \Sigma_M, \delta_M, m_0, F_M)$ and $N = (Q_N, \Sigma_N, \delta_N, n_0, F_N)$ be NFA-$\lambda$'s. A unique (up to isomorphism) product of $M$ and $N$ is given by the same as before, where
		\[ \delta : (Q_M \times Q_N) \times (\Sigma \cup \{\lambda\}) \to \pset{Q_M \times Q_N} \]
		is given by
		\[ ((q_m, q_n), a) \mapsto \begin{cases*}
			(\delta_M(q_m, \lambda) \times \{q_n\}) \cup (\{q_m\} \times \delta_N(q_n, \lambda)) & if $a = \lambda$ \\
			\delta_M(q_m, a) \times \delta_N(q_n, a) & otherwise
		\end{cases*} \]
	\end{lemma}
	\begin{definition}
		Let $M_1$ and $M_2$ be DFA/NFA/NFA-$\lambda$'s. We say that a DFA/NFA/NFA-$\lambda$ $M_1 \parallel M_2$ is the \textbf{parallel composition} of $M_1$ and $M_2$ if
		\[ \L(M_1 \parallel M_2) = \L(M_1) \cup \L(M_2) \]
	\end{definition}
	\begin{definition}
		Let $M = (Q_M, \Sigma_M, \delta_M, m_0, F_M)$ and $N = (Q_N, \Sigma_N, \delta_N, n_0, F_N)$ be NFA-$\lambda$'s. We say that the \textbf{parallel composition} of $M$ and $N$ is given by
		\[ M \parallel N := (Q_M \times Q_N, \Sigma, \delta, (m_0, n_0), F_M \times F_N) \]
		where $\Sigma := \Sigma_M \cup \Sigma_N$,
		\[ \delta : (Q_M \times Q_N) \times (\Sigma \cup \{\lambda\}) \to \pset{Q_M \times Q_N} \]
		is given by
		\[ ((q_m, q_n), a) \mapsto \begin{cases*}
			\delta_{M \times N}((q_m, q_n), a) & if $a \in (\Sigma_M \cap \Sigma_N) \cup \{\lambda\}$, \\
			\delta_M(q_m, a) \times \{q_n\} & if $a \in \Sigma_M$ but $a \notin \Sigma_N$, \\
			\{q_m\} \times \delta_N(q_n, a) & if $a \in \Sigma_N$ but $a \notin \Sigma_M$.
		\end{cases*} \]
		where $\delta_{M \times N}$ refers to the previous definition of $\delta$ for $M \times N$.
	\end{definition}
	\begin{definition}
		Let $\Sigma$ be an alphabet. Let $w \in \Sigma^*$. Let $\tilde \Sigma \subseteq \Sigma$.
		We say that the \textbf{projection} of $w$ \textbf{onto} $\tilde \Sigma$ (in $\Sigma$) is
			\[ w \upharpoonright \tilde \Sigma := \begin{cases*}
				(a \upharpoonright \tilde \Sigma)(v \upharpoonright \tilde \Sigma) & if $w = av$ for some $a \in \Sigma$ and $v \in \Sigma^*$, \\
					\lambda & otherwise.
			\end{cases*} \]
		where for $a \in \Sigma$ we define
		\[ a \upharpoonright \tilde\Sigma := \begin{cases*}
			a & if $a \in \tilde \Sigma$ \\
			\lambda & otherwise
		\end{cases*} \]
	\end{definition}
	\begin{definition}
		Let $\Sigma$ be an alphabet. Let $L \subseteq \Sigma^*$ be a language. Let $\tilde \Sigma \subseteq \Sigma$.
		We say that the \textbf{projection} of $L$ \textbf{onto} $\tilde \Sigma$ (in $\Sigma$) is
		\[ L \upharpoonright \tilde \Sigma := \{ w \upharpoonright \tilde \Sigma \mid w \in L \} \]
	\end{definition}
	\begin{definition}
		Let $\Sigma$ be an alphabet. Let $\tilde \Sigma \subseteq \Sigma$. Let $M = (Q, \Sigma, \delta, q_0, F)$ be an NFA-$\lambda$. We say that the \textbf{projection} of $M$ \textbf{onto} $\tilde \Sigma$ is the NFA-$\lambda$ $\tilde M := (Q, \tilde \Sigma, \tilde \delta, q_0, F)$ where
		\[ \tilde \delta : Q \times (\tilde \Sigma \cup \{ \lambda \}) \to \pset Q \]
		is given by
		\[ (q, a) \mapsto \delta(q, a) \cup  \begin{cases*}
			\displaystyle \bigcup_{\tilde a \in \Sigma \setminus \tilde \Sigma} \delta(q, \tilde a) & if $a = \lambda$, \\
			\varnothing & otherwise.
		\end{cases*} \]
	\end{definition}
	\begin{theorem}
		Let $M = (Q_M, \Sigma_M, \delta_M, m_0, F_M)$ and $N = (Q_N, \Sigma_N, \delta_N, n_0, F_N)$ be NFA-$\lambda$'s. Then, for all $w \in \Sigma^*$ where $\Sigma := \Sigma_M \cup \Sigma_N$, it holds that
		\[ w \in \L(M \parallel N) \iff w \upharpoonright \Sigma_M \in \L(M) \land w \upharpoonright \Sigma_N \in \L(N) \]
	\end{theorem}
	\newpage
	\section{Grammars}
	\begin{definition}
		Let
		\begin{itemize}
			\item $V$ be any finite set, called the \textbf{variables},
			\item $\Sigma$ be an alphabet, such that $V \cap \Sigma = \varnothing$,
			\item $P \subseteq V \times (V \cup \Sigma)^*$, called the \textbf{production rules},
			\item $S \in V$, called the \textbf{start symbol}.
		\end{itemize}
		The tuple $(V, \Sigma, P, S)$ is then called a \textbf{context free grammar}. If $(A, w) \in P$, we write $A \to w$, read `$A$ produces $w$'. If a sequence $(A, w_1), \ldots, (A, w_n) \in P$, we also write
		\[ A \to w_1 \mid \ldots \mid w_n \]
	\end{definition}
	\begin{definition}
		Let $(V, \Sigma, P, S)$ be a context-free grammar. Let $A \in V$ and $w \in (V \cup \Sigma)^*$ such that $A \to w$. If $u, v \in \Sigma^*$, we say that the $uwv$ is \textbf{derived from} the word $uAv \in (V \cup \Sigma)^*$. We sometimes write
		\[ u \mathbf{A}v \implies u\mathbf{w}v \]
	\end{definition}
	\begin{definition}
		Let $(V, \Sigma, P, S)$ be a context-free grammar. Let $v \in (V \cup \Sigma)^*$ be a string. We say that a set $D \subseteq (V \cup \Sigma)^*$ is \textbf{closed under derivation} (from $v$) if
		\begin{itemize}
			\item $v \in D$, and
			\item for all $x, y \in (V \cup \Sigma)^*$ such that $xAy$ and $(A \to w) \in P$, then $xwy \in D$.
		\end{itemize}
		We define the set $\operatorname{Der}(v)$ to be the smallest such set that contains $v$, i.e.
		\[ \operatorname{Der}(v) := \bigcap \{ D \subseteq (V \cup \Sigma)^* \mid v \in D \land D \text{ is closed under derivation} \} \]
		If $w \in \operatorname{Der}(v)$ we also write
		\[ v \stackrel{*}{\implies} w \]
		read: `$v$ \textbf{derives} $w$' or `$w$ is \textbf{derivable from} $v$'.
	\end{definition}
	\begin{definition}
		Let $(V, \Sigma, P, S)$ be a CFG. Let $w \in \Sigma^*$ be derivable from $S$, i.e. $S \stackrel{*}{\implies} w$. The \textbf{derivation tree} from $S$ to $w$ given a derivation is defined to be the tree with root $S$, such that when at a certain leaf with variable $A$, a certain rule $A \to x_1 \cdot \ldots \cdot x_n$ is applied, we add $x_1, \ldots, x_n$ as children to $A$ (where every $x_i \in V \cup \Sigma$).
	\end{definition}
	\begin{definition}
		A CFG $(V, \Sigma, P, S)$ is called \textbf{ambiguous} if multiple possible leftmost derivations/ derivation trees exist for a certain $w$ such that $S \stackrel{*}{\implies} w$.
	\end{definition}
	\begin{definition}
			Let $G = (V, \Sigma, P, S)$ be a CFG. Let $w \in (V \cup \Sigma)^*$.
			\begin{itemize}
					\item If $w$ is derivable from $S$, we call $w$ \textbf{sentential} in $G$
					\item If additionally $w \in \Sigma^*$ (it contains no variables), $w$ is called a \textbf{sentence} in $G$
					\item The set of all sentences in $G$ is called the \textbf{language} of $G$
					\[ \L(G) := \{ w \in \Sigma^* \mid S \stackrel{*}{\implies} w \} \]
				\end{itemize}
		\end{definition}
	\begin{definition}
		Let $\Sigma$ be an alphabet. Let $L \subseteq \Sigma^*$ be a language. We say that $L$ is \textbf{context-free} if a CFG $G$ with alphabet $\Sigma$ exists such that $\L(G) = L$.
	\end{definition}
	\begin{definition}
		Let $G_1, G_2$ be CFG's. We say that $G_1$ and $G_2$ are \textbf{equivalent} if their languages coincide, that is
		\[ \L(G_1) = \L(G_2) \]
	\end{definition}
	\subsection{Regular grammars}
	\begin{definition}
		A grammar $G$ is called \textbf{regular} if every rule is of the form (for some $A, B \in V$ and $a \in \Sigma$)
		\begin{itemize}
			\item $A \to a$, or
			\item $A \to aB$, or
			\item $A \to \lambda$.
		\end{itemize}
	\end{definition}
	\begin{remark}
		There exist equivalent CFG's where one is regular and the other is not (quite obviously, I suppose?).
	\end{remark}
	\begin{theorem}
		NFA languages (and thus regular languages) are context-free. Moreover (and we will not show this) for every regular grammar, there exists a DFA that accepts the same language, ergo, regular grammars and regular languages coincide.
	\end{theorem}
	\begin{proof}
		Let $M = (Q, \Sigma, \delta, q_0, F)$ be an NFA. Let $G = (Q, \Sigma, P, q_0)$ be a CFG where $P$ we will now construct. Remember that $\delta : Q \times \Sigma \to \pset Q$.
%		Let $q \in Q$, $a \in \Sigma$. We construct the set
%		\[ P_{q, a} := \{ q \to a \tilde q \mid \tilde q \in \delta(q, a) \} \]
%		and then
		We define 
		\[ P := \{ q \to a \tilde q \mid \tilde q \in \delta(q, a) \land q \in Q \land a \in \Sigma \} \cup \{ (q, \lambda) \mid q \in F \} \]
		Clearly, $P \subseteq (Q \cup \Sigma)^*$, $q_0 \in Q$, so yes, $G$ is a context free grammar. We show that $\L(M) = \L(G)$. Notice that every inference $[q, aw] \vdash [\delta(q, a), w]$ corresponds one-to-one with a derivation step $q \to a\delta(q, a)$, and from this essentially the rest of the proof follows.\\
		Because every NFA has a corresponding CFG that is regular, NFA languages are also context-free.
	\end{proof}
	\begin{remark}
		\textbf{Parsing} is the act of taking a word $w \in \L(G)$ for some unambiguous grammar $G$ and finding the derivation from the starting symbol.\\
		Unambiguous grammars exist for regular languages. 
	\end{remark}
	\newpage
	\subsection{Normal forms}
	\begin{lemma}
		Let $G = (V, \Sigma, P, S)$ be a grammar. Let $\tilde S \notin V \cup \Sigma$ be any set. Then
		\[ \tilde G := (V \cup \{ \tilde S \}, \Sigma, P \cup \{  \tilde S \to S \}, \tilde S) \]
		satisfies $\L(\tilde G) = \L(G)$.
	\end{lemma}
	\begin{proof}
		We show inclusion both ways. Let $w \in \L(G)$, suppose we have a derivation $S \stackrel{*}\implies w$, then clearly $\tilde S \implies S \stackrel * \implies w$ is a derivation for $w$ in $\tilde G$, whence $w \in \L(\tilde G)$.\\
		Now suppose $w \in \L(\tilde G)$. Its derivation starts with $\tilde S \to S$, because $\tilde S$ does not have any other production rules in $P$, since $\tilde S$ is not in $V$ or $\Sigma$, whence $S \stackrel * \implies w$ is a valid derivation of $w$ in $G$, whence $w \in \L(G)$.
	\end{proof}
	\begin{lemma}
		Let $G = (V, \Sigma, P, S)$ be a grammar. Let $u, v \in (V \cup \Sigma)^*$ and $A, B \in V$ such that there exists a set $\tilde P$ such that
		\[ P = \tilde P  \cup \{ A \to uBv \} \]
		Let
		\[ \tilde G := (V, \Sigma, P') \]
		with
		\[ P' := \tilde P \cup \{ (A \to uwv) \mid (B \to w) \in P, w \in (V \cup \Sigma)^* \} \]
		Then $\tilde G$ and $G$ are equivalent in the sense that $\L(\tilde G) = \L(G)$.
	\end{lemma}
	\begin{definition}
		Let $G = (V, \Sigma, P, S)$ be a CFG. We say that $G$ is in \textbf{Chomsky normal form} if for all rules $(A \to w) \in P$ for some $A \in V$ and $w \in (\Sigma \cup V)^*$ we have that either
		\begin{itemize}
			\item there exist $B, C \in V \setminus \{ S \}$ such that $w = BC$, or
			\item there exists $a \in \Sigma$ such that $w = a$, or
			\item $A = S$ and $w = \lambda$.
		\end{itemize}
	\end{definition}
	\begin{theorem}
		For every CFG, there exists an equivalent CFG in Chomsky normal form (CNF). That is, for all CFG's $G$, there exists $\tilde G$ in CNF such that $\L(G) = \L(\tilde G)$.
	\end{theorem}
	\begin{proof}
		We do this by explicit construction, that is, providing an algorithm to produce from any grammar $G = (V, \Sigma, P, S)$ an equivalent grammar in CNF. We do this in several steps. First of all, we use the lemma from before where we introduce a nonrecursive start symbol $S$ by introducing $\tilde S \to S$, so without loss of generality we can suppose the start symbol does not contain recursive production rules.\\ Let $N \subseteq V$ be the smallest set such that for all $A \in N$, there exists $w \in N^*$ such that $A \to w$ is a rule in $P$, as well as that $N$ that for all $A \in V$ such that $A \to \lambda$ is a rule in $P$, $A \in N$.\\
		In a sense, the set $N$ is the set of all variables for which a $\lambda$ derivation exists. We now define $P_1$, the set of production rules after the first step, $\lambda$-elimination. We first define $\tilde P \supseteq P$ by including all of $P$ and then for all $(A \to w) \in P$, if there exist $A_1, \ldots, A_k \in N$ and words $w_1, \ldots, w_{k+1} \in (\Sigma \cup V)^*$ such that
		\[ w = w_1 A_1 w_2 A_2 \cdot \ldots \cdot w_k A_k w_{k+1} \]
		we add $A \to w_1 w_2 \cdot \ldots \cdot w_{k+1}$ in $\tilde P$. Then we define
		\[ P_1 := \{ (A \to w) \in \tilde P \mid w = \lambda \implies A = S \} \]
		This is the set of rules after the first step. It is somewhat annoying but trivial to show that then $G_1 := (V, \Sigma, P_1, S)$ is an equivalent grammar that has no $\lambda$-productions except possibly $S \implies \lambda$.\\
		Let $A \in V$, then define the set
		\[ \operatorname{Chain}(A) := \{ B \in V \mid (A \stackrel * \implies B) \in P_1 \} \]
		Then we define $P_2$ to be the set of production rules where for all $A \in V$, $B \in \operatorname{Chain}(A)$, and $w \in (\Sigma \cup V)^*$ with $w \notin V$ and $B \to w$ in $P_1$, we add $A \to w$ in $P_2$, there exist no other rules. One may again show that $G_2 := (V, \Sigma, P_2, S)$ yields $\L(G_2) = \L(G_1) = \L(G)$.\\
		Finally, we bring $G_2$ to normal form. There exist no $\lambda$ productions and no chain rules, that is, transitive dependencies, in a sense. Therefore, every rule $A \to w$ with $|w| < 2$ already satisfies the CNF requirement. Now if $|w| \geq 2$ then we write
		\[ w = av \]
		for $a \in V \cup \Sigma$, $v \in (V \cup \Sigma)^*$. If $a \in \Sigma$, let $B$ be any set disjoint with $V$ and $\Sigma$, and update $V := V \cup \{ B \}$, so in a sense, without loss of generality, suppose $a \in V$. Then we define a new rule $w = aC$ for some new variable $C$ with update $V := V \cup \{C\}$ where $C$ has a single production rule, namely $C \to v$. We repeat this procedure, if necessary ($|v| \geq 2|$) for $C$. After this, we are left with an updated set of variables $\tilde V$ and an updated set of production rules $P_3$ such that $G_3 := (\tilde V, \Sigma, P_3, S)$ satisfies $\L(G_3) = \L(G_2) = \ldots = \L(G)$, and $G_3$ is in CNF is then left to show, which is true by construction (one may check this). 
%		\[ w = a_1 \cdot \ldots \cdot a_n \]
%		for $n = |w|$, $a_i \in V \cup \Sigma$ for all $i = 1, \ldots, n$.
	\end{proof}
	\subsection{Optimization of CNF}
	One may detect rules that do not terminate by backwardsly substituting all rules that DO terminate, which gives a set $T \subseteq V$ for a grammar $G = (V, \Sigma, P, S)$ in CNF for which all inferences of $T$ do not result in loops. We define
	\[ \tilde P := \{ (A \to w) \in P \mid A \in T \} \]
	and then $\tilde G := (T, \Sigma, \tilde P, S)$ is an equivalent grammar, still in CNF (because we just deleted rules).\\
	Likewise, we may find the set of unreachable variables (ones that may never be produced) by first finding the set of all variables that do get produced by forwardsly substituting, starting with just the set containing the starting variable. Let $R \subseteq V$ be the set of all reachable variables, that is, all variables for which there exists a derivation from $S$ to a word that contains that variable. Then $\tilde G := (R, \Sigma, \tilde P, S)$ with
	\[ \tilde P := \{ (A \to w) \in P \mid A \in R \} \]
	yields an equivalent grammar, that is potentially smaller.\\
	\textbf{Summary}: to optimize the CNF (or any grammar, really), we first delete all nonterminating variables, and then we delete all unreachable variables.
	\subsection{CYK parsing}
	Let $G = (V, \Sigma, P, S)$ be a grammar in CNF. Let $w \in (\Sigma \cup V)^*$ be a word to be parsed (remember, that means finding a derivation for it, finding a parse tree). Let $w = a_1 \cdot \ldots \cdot a_n$ for $n \in \N$, $a_i \in V \cup \Sigma$ for all $i = 1, \ldots, n$. We define the subword $w_{i, j}$ for all $1 \leq i \leq j \leq n$ and $i, j \in \N$ by
	\[ w_{i, j} := a_i \cdot a_{i+1} \cdot \ldots \cdot a_j \]
	Then we define the set $X_{i, j} \subseteq V$ to be the set of variables that have a derivation to $w_{i, j}$. This set can be found by \textbf{dynamic programming}. Start first with the set $X_{i, j}$ with $i = j$. This is easy, (the base case)
	\[ X_{i, i} := \{ A \in V \mid (A \to a_{i, i}) \in P \} \]
	Then for all $L = 2, \ldots, n$, in that order, and all $i = 1, \ldots, n - L + 1$, take $j := i + L$ ($L$ is thus the length of the subword we try to parse), then a variable $A$ may parse $w_{i, j}$ only if there exists a rule $A \to BC$ such that $B$ can parse a part of it, and $C$ can parse the other part, i.e.
	\[ X_{i, j} := \{ A \in V \mid \exists k = i, \ldots, j-1: \exists B \in X_{i, k}, C \in X_{k+1, j} : (A \to BC) \in P \} \]
	and indeed if we iterate in the appropriate order, this will work out. Now clearly $w \in \L(G)$ if and only if $S \in X_{1, n}$, but this is not yet the same as parsing, of course. Though, the derivation tree may be readily read off `tracing the algorithm backwards'.
	\newpage
	\section{Pushdown automata}
	\begin{definition}
		Let $X$ be any set that does not contain the empty word $\lambda$. We define (for convenience) the set $X^\lambda := X \cup \{\lambda\}$.
	\end{definition}
	\begin{definition}
		Let 
		\begin{itemize}
			\item $Q$ be any set, the \textbf{set of states},
			\item $\Sigma$ and $\Gamma$ be alphabets, called the \textbf{input} and \textbf{stack} alphabets, respectively,
			\item $\delta : Q \times \Sigma^\lambda \times \Gamma^\lambda \to \pset{\Gamma^\lambda \times Q}$, the \textbf{transition function},
			\item $q_0 \in Q$, the \textbf{initial state},
			\item $F \subseteq Q$, the \textbf{accepting states}.
		\end{itemize}
		Then the tuple $(Q, \Sigma, \Gamma, \delta, q_0, F)$ is called a \textbf{pushdown automaton}. Note that the book models $\delta$ as a relation
		\[ \delta \subseteq Q \times \Sigma^\lambda \times \Gamma^\lambda \times \Gamma^\lambda \times Q \]
	\end{definition}
	\begin{definition}
		Let $M = (Q, \Sigma, \Gamma, \delta, q_0, F)$ be a pushdown automaton. We say that a tuple $(q, w, \alpha) \in Q \times \Sigma^* \times \Gamma^*$ is a \textbf{configuration} of the automaton. We define the relation $\vdash$ on configurations by:
		If $(q, a, o, i, \tilde q) \in \delta$ and there exists $v \in \Sigma^*$ such that $w = av$ and there is some $\beta \in \Gamma^*$ such that $\alpha = o \beta$ ($a, o = \lambda$ is also possible) then
			\[ (q, av, o \beta) \vdash (\tilde q, v, i \beta) \]
		We define $\vdash^*$ to be the reflexive-transitive closure of $\vdash$. Then we define the \textbf{language} of the automaton through
		\[ \L(M) := \{ w \in \Sigma^* \mid \exists q \in F : (q_0, w, \lambda) \vdash^* (q, \lambda, \lambda) \} \]
	\end{definition}
	\begin{remark}
		Clearly, every NFA-$\lambda$ and thus every other automaton discussed so far can be transformed into a pushdown automaton by having an empty / arbitrary stack alphabet, and never pushing to the stack in $\delta$. But, we can show that for example, the \textbf{non-regular} language
		\[ \{ a^i b^i \mid i \in \N \} \]
		is definable through a pushdown automaton: let $Q := \{q_0, q_1\}$, $\Sigma := \{a, b\}$, $\Gamma := \{a\}$, $F := \{q_1\}$, then
		\[ \delta := \{ (q_0, a, \lambda, a, q_0), (q_0, b, a, \lambda, q_1), (q_1, b, a, \lambda, q_1) \} \]
	\end{remark}
	\begin{definition}
		We say that the transitions $(q, x_1, A_1, B_1, \tilde q_1), (q, x_2, A_2, B_2, \tilde q_2) \in \delta$ overlap if
		\begin{itemize}
			\item $x_1 = x_2$, or at least one of $x_1, x_2$ is $\lambda$, and
			\item $A_1 = A_2$, or at least one of $A_1, A_2$ is $\lambda$
		\end{itemize}
		Intuitively, this means that you `cannot tell' which transition will happen.
	\end{definition}
	\begin{definition}
		Let $M = (Q, \Sigma, \Gamma, \delta, q_0, F)$ be a PDA. We say that $M$ is \textbf{deterministic} if for any two transitions $\delta_1, \delta_2 \in \delta$, if $\delta_1$ and $\delta_2$ overlap, then $\delta_1 = \delta_2$, i.e. no distinct overlapping transitions exist.
	\end{definition}
	\begin{example}
		Let $\Sigma$ be any alphabet. Let
		\[ L := \{ ww^R \mid w \in \Sigma^* \} \]
		be the language of palindromes. Recall that $L$ is non-regular. But we can construct the PDA $M := (Q, \Sigma, \Sigma, \delta, q_0, F)$ where $Q := \{q_0, q_1\}$, $F := \{q_1\}$, and
		\[ \delta := \{ (q_0, a, \lambda, a, q_0) \mid a \in \Sigma \} \cup \{ (q_1, a, a, \lambda, q_1) \mid a \in \Sigma \} \cup \{ (q_0, \lambda, \lambda, \lambda, q_1) \} \]
		Then $\L(M) = L$. Note that $M$ is \textbf{not} deterministic (check!).
	\end{example}
	\begin{remark}
		In the remainder of the lecture this section belongs to, we research whether CFG languages and PDA languages are equivalent. But we can already say something about unambiguity not being equivalent to determinism on PDA's: note that the language of palindromes has the unambiguous grammar $(V, \Sigma, P, S)$ where $V = \{S\}$, and
		\[ P := \{ S \to a S a \mid a \in \Sigma \} \cup \{S \to \lambda \} \]
		is unambiguous, but no deterministic PDA exists.
	\end{remark}
	\begin{definition}[Alternative notions of the language of a PDA]
		Let $M := (Q, \Sigma, \Gamma, \delta, q_0, F)$ be a PDA. We define the \textbf{final state language} $\L_F(M)$ of $M$ through
		\[ \L_F(M) := \{ w \in \Sigma^* \mid \exists q \in F : \exists \alpha \in \Gamma^* : (q_0, w, \lambda) \vdash^* (q, \lambda, \alpha) \} \]
		We define the \textbf{empty stack language} $\L_E(M)$ of $M$ through
		\[ \L_E(M) := \{ w \in \Sigma^* \mid \exists q \in Q : (q_0, w, \lambda) \vdash^* (q, \lambda, \lambda) \} \]
	\end{definition}
	\begin{lemma}
		$\L(M) \subseteq \L_F(M)$
	\end{lemma}
	\begin{lemma}
		Let $M := (Q, \Sigma, \Gamma, \delta, q_0, F)$ be a PDA. Then there exists a PDA $\tilde M$ such that
		\[ \L(M) = \L_F(\tilde M) \]
	\end{lemma}
	\begin{proof}
		Let $q_s, q_f \notin Q$ be any sets, let $Z \notin \Gamma$ also be any set. Define $\tilde Q := Q \cup \{q_s, q_f\}$, $\tilde \Gamma := \Gamma \cup \{Z\}$, and
		\[ \tilde \delta := \delta \cup \{ (q_s, \lambda, \lambda, Z, q_0) \} \cup \{ (q, \lambda, Z, \lambda, q_f) \mid q \in F \} \]
		Then the PDA $\tilde M := (\tilde Q, \Sigma, \tilde \Gamma, \tilde \delta, q_s, \varnothing)$ by construction satisfies $\L_F(\tilde M) = \L(M)$.
	\end{proof}
	\begin{lemma}
		Let $M := (Q, \Sigma, \Gamma, \delta, q_0, F)$ be a PDA. Then there exists a PDA $\tilde M$ such that
		\[ \L_F(M) = \L(\tilde M) \]
	\end{lemma}
	\begin{proof}
		Let $q_f \notin Q$ be any set. Define $\tilde Q := Q \cup \{q_f\}$, $\tilde F := \{q_f\}$ and
		\[ \tilde \delta := \delta \cup \{ (q, \lambda, \lambda, \lambda, q_f) \mid q \in F \} \cup \{ (q_f, \lambda, a, \lambda, q_f) \mid a \in \Gamma \} \]
		Then the PDA $\tilde M := (\tilde Q, \Sigma, \Gamma, \tilde \delta, q_0, \tilde F)$ by construction satisfies $\L(\tilde M) = \L_F(M)$.
	\end{proof}
	\begin{corollary}
		We cannot define more languages through the final language of a PDA than we already could with PDA's.
	\end{corollary}
	\begin{remark}
		In the above proofs we pick arbitrary sets disjoint of $Q$ for example, like the $q_s$, $q_f$. In order to avoid this, we can use the disjoint union instead, if desired.
	\end{remark}
	\begin{remark}
		Pretty much the same proofs and constructions (in spirit) we can do for $\L_E$, but it bores me.
	\end{remark}
	\begin{definition}
		An \textbf{extended pushdown automaton} is a PDA with instead a transition relation
		\[ \delta \subseteq Q \times \Sigma^\lambda \times \Gamma^\lambda \times \Gamma^* \times Q \]
		The appropriate languages associated with such an automaton are the same as before, where we define the inference relation of the configuration: if $(q, a, A, W, \tilde q) \in \delta$, then
		\[ (q, aw, A \alpha) \vdash (\tilde q, w, W \alpha) \]
		Note that $A \in \Gamma$ whereas $W \in \Gamma^*$. Perhaps we use $W^R$ if that is intuitively more clear.
	\end{definition}
	\begin{theorem}
		The class of extended PDA's and regular ones are equivalent, that is, for every extended PDA there exists an equivalent regular PDA. The reverse is of course trivial through the embedding $\Gamma \to \Gamma^*$ where $w \mapsto w$.
	\end{theorem}
	\newpage
	\subsection{Relation to CFGs}
	\begin{definition}
		Let $G = (V, \Sigma, P, S)$ be a CFG. $G$ is said to be in \textbf{Greibach normal form} if for all $(A \to w) \in P$ it holds that either 
		\begin{itemize}
			\item $A = S$ and $w = \lambda$, or
			\item there exists $a \in \Sigma^\lambda$ and $B_1, \ldots, B_n \in (V \cup \Sigma)^* \setminus \{S\}$ such that
			\[ w = a B_1 \cdot \ldots \cdot B_n \]
		\end{itemize}
	\end{definition}
	\begin{theorem}
		For every CFG $G$ in GNF (Greibach normal form) there exists an extended PDA $M$ such that $\L(M) = \L(G)$ and the PDA $M$ has two states.
	\end{theorem}
	\begin{proof}
		Let $G = (V, \Sigma, P, S)$ be in GNF. Let $q_0, q_1$ be any sets. We define \[M := (\{q_0, q_1\}, \Sigma, V\setminus \{S\}, \delta, \{q_1\})\] where $\delta$ is given by:
		\begin{itemize}
			\item If $(S \to \lambda) \in P$, then $(q_0, \lambda, \lambda, \lambda, q_1) \in \delta$,
			\item Then any other rule is of the form $(A \to aW) \in P$ with $a \in \Sigma^\lambda$ and $W \in V^*$. Define
			\[ B := \begin{cases*}
				A & if $A \neq S$, \\
				\lambda & otherwise.
			\end{cases*}, \qquad q := \begin{cases*}
				q_0 & if $A = S$ \\ 
				q_1 & otherwise
			\end{cases*} \]
			Then $(q, a, B, W, q_1) \in \delta$
		\end{itemize}
		Through this construction, $\L(M) = \L(G)$.
	\end{proof}
	\begin{theorem}
		For every CFG $G$ there exists a CFG $\tilde G$ in GNF such that $\L(G) = \L(\tilde G)$.
	\end{theorem}
	\begin{theorem}
		For every PDA $M$ there exists a CFG $G$ such that $\L(G) = \L(M)$.
	\end{theorem}
	\begin{remark}
		The result of all of this: the class of PDA's and CFG's are also the same.
	\end{remark}
	\subsection{Pumping lemma for CFLs}
	\begin{lemma}
		Let a grammar $G$ be in CNF. Let $w \in \L(G)$. If a parse tree for $w$ has a longest path of length $n \in \N^*$, then $|w| \leq 2^{n-1}$.
	\end{lemma}
	\begin{lemma}
		Let $L$ be a context-free language. Then there exists a $k > 0$ such that for all words $z \in L$ with $|w| \geq k$, we can write $z = uvwxy$ for some $u, v, w, x, y \in \Sigma^*$ with $|vwx| \leq k$, $vx \neq \lambda$, and for all $i \in \N$, $uv^iwx^iy \in L$.
		%		Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA.
	\end{lemma}
	\subsection{Properties of CFLs}
	\begin{theorem}
		The class of context-free languages is closed under union, concatenation and Kleene Star. It is, however, not closed under complement or intersection.
	\end{theorem}
	\begin{proof}
		Let $L, M$ be context-free languages, let $G_L = (V_L, \Sigma_L, P_L, S_L)$ and $G_M = (V_M, \Sigma_M, P_M, S_M)$ be CFGs that generate $L$ and $M$, respectively. Then
		\begin{itemize}
			\item The union $L \cup M$ is generated by taking any set $S \notin V_L \cup V_M$ and defining
			\[ \tilde G := (V_L \cup V_M \cup \{S\}, \Sigma_L \cup \Sigma_M, \tilde P, S) \]
			where
			\[ \tilde P := P_L \cup P_S \cup \{ S \to S_L, S \to S_M \} \]
			Then $\L(\tilde G) = L \cup M$.
			\item The concatenation $LM$ is generated by defining
			\[ \tilde G := (V_L \cup V_M, \Sigma_L \cup \Sigma_M, \tilde P, S_L) \]
			where
			\[ \tilde P := \{ (A \to w) \in P_L \mid A \neq S_L \} \cup P_S \cup \{ (S_L \to wS_M) \mid (S_L \to w) \in P \} \]
			Then $\L(\tilde G) = LM$.
			\item Take any set $S \notin V_L$ and define
			\[ \tilde G := (V_L \cup \{S\}, \Sigma_L, \tilde P, S) \]
			where
			\[ \tilde P := P_L \cup \{ S \to S_LS, S \to \lambda \} \]
			Then $\L(\tilde G) = L^*$.
		\end{itemize}
		The intersection property can be proven by counterexample. Then, of course, it would be a contradiction if the class were closed under union and complement but not intersection.
	\end{proof}
	\begin{theorem}
		The intersection of a regular and a context-free language is context-free.
	\end{theorem}
	\begin{proof}
		Let $M = (Q_M, \Sigma_M, \delta_M, q_{M, 0}, F_M)$ be a DFA that generates a regular language, and let $N = (Q_N, \Sigma_N, \Gamma_N, \delta_N, q_{N, 0}, F_N)$ be a PDA that generates a context-free language. Define the PDA
		\[ M \times N := (Q_M \times Q_N, \Sigma_M \sqcup \Sigma_N, \Gamma_N, \delta, (q_{M, 0}, q_{N, 0}), F_M \times F_N) \]
		where $\delta$ is defined to be the smallest set that satisfies
		\begin{itemize}
			\item If $(q_N, a, B, C, \tilde Q_N) \in \delta_N$ and $q_M \in Q_M$ where $a \neq \lambda$, then define $\tilde q_M := \delta_M(q_M, a)$ and
			\[ ((q_M, q_N), a, B, C, (\tilde Q_M, \tilde Q_N)) \in \delta \]
			\item If $(q_N, \lambda, B, C, \tilde Q_N) \in \delta_N$ and $q_M \in Q_M$, then
			\[ ((q_M, q_N), \lambda, B, C, (\tilde Q_M, Q_N)) \in \delta \]
		\end{itemize}
		By construction, $\L(M \times N) = \L(M) \cap \L(N)$.
	\end{proof}
	\newpage
	\section{Turing machines}
	\begin{definition}
		Let
		\begin{itemize}
			\item $Q$ be any finite set of states,
			\item $\Gamma$ be any alphabet called the \textbf{tape alphabet},
			\item $B \in \Gamma$, called the \textbf{blank element} on the tape,
			\item $\Sigma \subseteq \Gamma \setminus \{B\}$, called the \textbf{input alphabet},
			\item $\delta : Q \times \Gamma \rightharpoonup \Gamma \times \{L, R\} \times Q$, the \textbf{transition relation}, where $L := -1$ and $R := 1$,
			\item $q_0 \in Q$ the \textbf{start state},
			\item $F \subseteq Q$ a set of \textbf{final states}.
		\end{itemize}
		Then we call the tuple $M := (Q, \Sigma, \Gamma, \delta, q_0, F)$ a \textbf{Turing machine}.\\
		A \textbf{configuration} of a Turing machine $M$ is a tuple $(q, S, i, w) \in Q \times \Gamma^\Z \times \Z$, where
		\begin{itemize}
			\item $q$ is the \textbf{current state},
			\item $S : \Z \to \Gamma$ is the \textbf{current tape}, with the property that there exists $N \in \N$ such that for all $|j| \geq N$, $S(j) = B$,
			\item $i$ is the \textbf{current index} in the tape.
		\end{itemize}
		The relation $\vdash$ on these configurations is defined by: if $\delta(q, S(i)) = (\gamma, M, \tilde q)$, then
		\[ (q, S, i) \vdash (\tilde q, \tilde S, i + M) \]
		where $\tilde S : \Z \to \Gamma$ is defined by
		\[ \tilde S(j) := \begin{cases*}
			S(j) & if $j \neq i$ \\
			\gamma & otherwise.
		\end{cases*} \]
		We denote by $\vdash^*$ the reflexive-transitive closure of $\vdash$. We say that a Turing machine $M$ \textbf{accepts a word} $w \in \Sigma^*$ if there exists an inference $(q_0, S_0, 1) \vdash^* (q, \tilde S, \tilde i)$ for some $q \in F$, $\tilde S$ any tape, $\tilde i \in \Z$, where $S_0 : \Z \to \Sigma$ is defined by writing $w = a_1 \cdot \ldots \cdot a_n$ for some $n \in \N$ and $a_i \in \Sigma$ for all $i = 1, \ldots, n$, and
		\[ S_0(j) := \begin{cases*}
			a_j & if $1 \leq j \leq n$, \\
			B & otherwise.
		\end{cases*} \]
		such that also, $\delta(q, \tilde S(\tilde i))$ is not defined (we say the Turing machine \textbf{halts}).\\
		The \textbf{language} of $M$ is defined by
		\[ \L (M) := \{ w \in \Sigma^* \mid w \text{ is accepted by } M \} \]
	\end{definition}
	\begin{definition}
		Let $M$ be a Turing machine. We say that $M$ decides the language $L$ if $\L(M) = L$ and for all words $w \in \Sigma^*$, there exists a finite sequence of inference relations like in the above, $(q_0, S_0, 1) \vdash^* (q, \tilde S, \tilde i)$, where $q \in F$ may or may not be true. In other words, the Turing machine \textbf{halts for all inputs} (in the given alphabet).
	\end{definition}
	\begin{definition}
		Let $L$ be any language over an alphabet $\Sigma$. We say that $L$ is
		\begin{itemize}
			\item \textbf{recursively enumerable} if there exists a TM $M$ such that $\L(M) = L$,
			\item \textbf{recursive} if there exists a TM $M$ such that $\L(M) = L$ and $M$ decides $L$.
		\end{itemize}
	\end{definition}
	\begin{theorem}
		The class of recursive languages is bigger than the class of context-free languages, that is, all context-free languages can be defined by a TM but the reverse is false.
	\end{theorem}
	\begin{proof}
		Note that every PDA has an embedding into the class of TM. But there exists a Turing machine $M$ with
		\[ \L(M) = \{ a^i b^i c^i \mid i \in \N \} \]
		which is \textbf{not} context-free.
%		Let $(Q, \Sigma, \Gamma, \delta, q_0, F)$ be a PDA with
%		\[ \delta \subseteq Q \times \Sigma^\lambda \times \Gamma^\lambda \times \Gamma^\lambda \times Q \]
	\end{proof}
	\begin{remark}
		Many variations of TM exist. All are equivalent. Very boring, but cool to see that practically every extension / stronger model of computation is actually the same. The following variations do nothing
		\begin{itemize}
			\item More tapes
			\item Multiple tracks per tape
			\item Non-determinism
			\item Two-way tapes
		\end{itemize}
	\end{remark}
	\subsection{Katharsis}
	\begin{definition}
		An \textbf{(unrestricted) grammar} is a tuple $(V, \Sigma, P, S)$ where
		\begin{itemize}
			\item $V$ is a finite set of variables,
			\item $\Sigma$ is an alphabet, such that $V \cap \Sigma = \varnothing$,
			\item $P$ is a binary relation from $(V \cup \Sigma)^+$ to $(V \cup \Sigma)^*$, the set of production rules,
			\item $S \in V$ the \textbf{start symbol}.
		\end{itemize}
		The grammar is called \textbf{context-free} if every $(A \to w) \in P$ has $A \in V$ (this restores the original CFG definition).
	\end{definition}
	\begin{definition}
		Let $G = (V, \Sigma, P, S)$ be a grammar. Let $A \in (V \cup \Sigma)^+$ and $w \in (V \cup \Sigma)^*$ such that $(A \to w) \in P$. If $u, v \in (\Sigma \cup V)^*$, we say that the $uwv$ is \textbf{derived from} the word $uAv$. We sometimes write
		\[ uAv \implies uwv \]
		Like before, we define the relation $\stackrel * \implies$ by chains of derivations with $\implies$. The \textbf{language} of $G$ like before is
		\[ \L(G) := \{ w \in \Sigma^* \mid S \stackrel * \implies w \} \]
	\end{definition}
	\begin{theorem}
		Let $L$ be any language. $L$ is recursively enumerable if and only if there exists an unrestricted grammar $G$ such that $\L(G) = L$.
	\end{theorem}
	\begin{remark}
		Turing machines can
		\begin{itemize}
			\item Simulate all grammars, including context-free, including regular
			\item Simulate nondeterministic Turing machines
		\end{itemize}
		And they are equivalent to unrestricted grammars as well. This gives rise to the Chomsky hierarchy
		\begin{table}[H]
			\centering
			\begin{tabular}{c|c|c|c}
				Type & Languages & Grammars & Machines \\
				\hline
				0 & Recur. enum. & Unrestricted & TM \\
				(1) & (context-sensitive) & & (LBA) \\
				2 & CFL & CFG & PDA \\
				3 & Regular & Regular & (Regexp) DFA, NFA(-$\lambda$)
			\end{tabular}
		\end{table}
		Horizontally, entries are equivalent. Vertically down, the top row includes the bottom row as class of languages.
	\end{remark}
	\subsection{Universality}
	Let $M$ be a Turing machine. Suppose we can embed $M$ into binary, that is, we have $R(M) \in \{0, 1\}^*$. Can we make a Turing machine $U$ that can simulate $M$? This should have the property that for all TM $M$ and words $w$ in the alphabet of $M$, we have
	\begin{itemize}
		\item If input $w$ terminates in $M$, then $R(M)w$ must terminate in $U$,
		\item If input $w$ does not terminate in $M$, then $R(M)w$ must not terminate in $U$
	\end{itemize}
	Note that this is already impossible because the alphabet of $U$ is then the set of all sets. Shucks. We can either
	\begin{itemize}
		\item Make an embedding of words $w$ into binary, or
		\item suppose that words $w \in \{0, 1\}^*$ are already binary.
	\end{itemize}
	Is this possible? Yes, this is a personal computer. The hypothesis is that any algorithm can be encoded in a Turing machine.
	\begin{definition}
		Let $A \subseteq B$. A \textbf{decision problem} is the problem of finding an algorithm that can decide whether for any $b \in B$, also if $b \in A$. A Turing Machine $M$ \textbf{solves the decision problem} if
		\begin{itemize}
			\item there exists an encoding $R : B \to \{0, 1\}^*$,
			\item the tape alphabet of $M$ includes $\{0, 1\}^*$,
			\item $M$ always halts for any input,
			\item for all $b \in B$, let $q \in Q$ be the final state of $M$ with input $R(b)$, then $q \in F \iff b \in A$.
		\end{itemize}
		In other words, $M$ always `makes up its mind' on whether $b \in A$ by ending in an accepting state, or not.\\
		We say that a decision problem is \textbf{decidable} if there exists a Turing machine that decides it.
	\end{definition}
	\begin{remark}
		Note that from this definition it immediately follows that the language of $M$ is $R(A)$, which then must be recursive.
	\end{remark}
\end{document}