\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{hyperref}
\hypersetup{colorlinks,citecolor=black,filecolor=black,linkcolor=black,urlcolor=black}
\usepackage{enumerate}
\usepackage{lmodern}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{mdframed}
\usepackage{tikz}
\usetikzlibrary{automata}

\title{Notes on 1657+1658}
\author{Daniel Maslowski}

\newtheorem{defi}{Definition}
\newtheorem{theo}{Theorem}
\newtheorem{proof}{Proof}

\providecommand{\oo}[1]{\operatorname{o}\left(#1\right)}
\providecommand{\OO}[1]{\operatorname{O}\left(#1\right)}

\newcommand{\NN}{\mathbb{N}}
\newcommand{\LL}{\mathcal{L}}
\newcommand{\set}[1]{\mathrm{#1}}
\newcommand{\sym}[1]{\mathrm{#1}}
\newcommand{\str}[1]{\boldsymbol{\mathrm{#1}}}
\newcommand{\eps}{\str\varepsilon}

\newcommand{\wang}[6]{
\draw[fill=#3] +(#1+0,#2+0) -- +(#1+0.5,#2+0.5) -- +(#1+0,#2+1) -- +(#1+0,#2+0);
\draw[fill=#4] +(#1+1,#2+1) -- +(#1+0.5,#2+0.5) -- +(#1+1,#2+0) -- +(#1+1,#2+1);
\draw[fill=#5] +(#1+1,#2+1) -- +(#1+0.5,#2+0.5) -- +(#1+0,#2+1) -- +(#1+1,#2+1);
\draw[fill=#6] +(#1+0,#2+0) -- +(#1+0.5,#2+0.5) -- +(#1+1,#2+0) -- +(#1+0,#2+0);
}
\newcommand{\tile}[6]{
\draw +(#1,#2) rectangle +(#1+1,#2+1);
\draw +(#1+1,#2) -- +(#1,#2+1);
\draw +(#1,#2) -- +(#1+1,#2+1);
\node at (#1+0.2,#2+0.5) {#3};
\node at (#1+0.8,#2+0.5) {#4};
\node at (#1+0.5,#2+0.8) {#5};
\node at (#1+0.5,#2+0.2) {#6};
}


\begin{document}

\maketitle
\tableofcontents

\pagebreak
\begin{abstract}
  The following document mainly reduces the content of the courses 1657 and 1658 ("Grundlagen der Theoretischen Informatik A/B") of the FernUniversität in Hagen to the definitions, theorems and proofs provided by the authors. They may somewhat differ from common definitions found in textbooks. However, when I felt that a definition, theorem or proof did not satisfy me for some reason, I might as well have chosen to modify them, sometimes slightly, sometimes completely, to gain consistency. See this as a general quick reference for anyone. Hence I neither guarantee correctness nor completeness.
\end{abstract}


\pagebreak
\section{Introduction}
  Theoretical Computer Science consists of several larger topics, three of which are mainly formal languages, automata, and computability.\\

  Although the course starts with some automata, I decided to collect the definitions of all the automata mentioned (and some more) in one section. Thus the order of this summary differs from the original order of the course material where automata are defined just where needed. I don't like this hide-and-seek approach though. In addition, I will start introducing formal languages first, like many textbooks do.\\


\pagebreak
\section{Formal languages}

  \subsection{Basic terms}\ \\
  \fbox{\parbox{\linewidth}{
    \begin{defi}[Formal language]\ \\
      A formal language $\mathcal{L}$ is a set of strings (words) on some alphabet $\Sigma$, i.e. $\mathcal{L} \subseteq \Sigma^*$.
    \end{defi}
    \begin{defi}[Alphabet]\ \\
      An alphabet $\Sigma = \{\sym a,\sym b,\sym c, ...\}$ is a set of symbols.\\
      Its cardinality (number of elements) is usually denoted as $|\Sigma|$.
    \end{defi}
    \begin{defi}[String]\ \\
      A string (word) $\str x$ is an ordered list of symbols, often denoted in bold face.\\
      The length of a string is usually denoted as $|\str{x}|$.\\
      The empty string $\eps$ is the only string of length $0$.\\
      For an alphabet $\Sigma$, $\Sigma^i$ is the set of all strings of length $i$ on $\Sigma$.
    \end{defi}
    \begin{defi}[Kleene closure]\ \\
      The Kleene closure $\Sigma^*=\bigcup_{i\in\NN}\Sigma^i$, provided by the star operator $^*$, is the set of all strings of any length on an alphabet $\Sigma$, including the empty string $\eps$.\\
      The plus operator $^+$, similar to the star operator, gives the set of all non-empty strings on an alphabet $\Sigma$, i.e. the Kleene closure excluding the empty string: $\Sigma^+ = \Sigma^*\backslash\{\eps\}$.
    \end{defi}
    \begin{defi}[Concatenation]\ \\
      The concatenation of two strings $\str z=\str{xy}$ is the ordered list of symbols that results from adding the symbols in $\str y$ to $\str x$, keeping their order. It can be arithmetically seen as a multiplication and an addition: $\str z=\str x*|\Sigma|^{|\str y|}+\str y$. As a shorthand notation, the $i$-times repeated concatenation of a string $\str x$ with itself is denoted as $\str x^i$.\\
      For convenience: $\str x^0=\eps$, $\str x^1=\str x$.\\
      The concatenation of two languages $\LL_{12} = \LL_1\LL_2$ is the set of all strings that result from concatenating all strings from $\LL_1$ with all strings from $\LL_2$.\\
      As a shorthand notation, similar to the cartesian product, the $i$-times repeated concatenation of a language $\LL$ with itself is denoted as $\LL^i$.\\
      For convenience: $\LL^0=\{\eps\}$, $\LL^1=\LL$, $(\forall i\geq1) \varnothing^i=\varnothing$.
    \end{defi}
  }}

  \pagebreak    
  \subsection{The Chomsky Hierarchy}\ \\
  \fbox{\parbox{\linewidth}{
    \begin{defi}[Formal grammar]\ \\
      A formal grammar is a 4-tuple $(\set N, \Sigma,\set P,\sym s)$ consisting of an alphabet of non-terminal symbols $\set N$, an alphabet of terminal symbols $\Sigma$ s.t. $\set N \cap \Sigma = \varnothing$, a set of production rules $\set P$ and a start symbol $\sym s \in \set N$.
    \end{defi}

%       A production rule is ...

%       ... binary relation $x \xrightarrow[G]{i} y$, s.t. $x$.\\

    \begin{defi}[Regular language]\ \\
      A regular language is a language produced by a regular grammar.
    \end{defi}
  }}

  \pagebreak

  \subsection{Pumping lemma}\ \\
  \fbox{\parbox{\linewidth}{
    \begin{theo}[Pumping lemma for regular languages]\ \\
      $\mathcal{L} \: regular \Rightarrow \exists p \in \NN \: s.t. \; (\forall \mathrm{z} \in \mathcal{L}, |\mathrm{z}| \geq p) \: \exists \mathrm{uvw}=\mathrm{z} \: s.t.$
      \begin{enumerate}
        \item $|\mathrm{uv}| \le p$
        \item $|\mathrm{v}| \geq 1)$
        \item $(\forall i \in \NN) \: \mathrm{uv^iw} \in \mathcal{L}$
      \end{enumerate}
    \end{theo}

    \begin{theo}[Pumping lemma for context-free languages]\ \\
      $\mathcal{L}\: context\text{-}free \Rightarrow \exists p \in \NN \: s.t. \: (\forall \mathrm{z} \in \mathcal{L}, |\mathrm{z}| \geq p) \: \exists \mathrm{luvwr}=\mathrm{z} \: s.t.$
      \begin{enumerate}
        \item $|\mathrm{uvw}| \le \mathrm{p}$
        \item $|\mathrm{uw}| \geq 1$ 
        \item $(\forall i \in \NN) \: \mathrm{lu^ivw^ir} \in \mathcal{L}$
      \end{enumerate}
    \end{theo}
  }}


\pagebreak
\section{Automata}
Example automaton\\
  \begin{tikzpicture}[shorten >=1pt,node distance=2cm,auto]
    \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}


\pagebreak
\section{Computability}
  This section lists the definitions from the chapters on computability.\\

  There are three very similar main sets that we look at throughout the course: The set of positive integers including $0$ ($\NN$), the set of all words on some alphabet $\Sigma$ including the empty word $\eps$ ($\Sigma^*$) as mentioned in the first chapter and the set of all words of infinite length on some alphabet $\Sigma$ ($\Sigma^\omega$). For the reason of this diversity, many of the following definitions and theorems are provided differently for the respective sets.\\

% codomain = image (range, Ran(f)) <=> surjection
% an element of the codomain is mapped to by at most one element of the domain (Dom(f)) <=> injection



  \subsection{Numberings, notations, and representations}\ \\
  \fbox{\parbox{\linewidth}{
    \begin{defi}[Numbering]\ \\
      A $numbering$ is a surjective function $\nu: \subseteq \NN \rightarrow M$.\\
    \end{defi}
    \begin{defi}[$(\nu_1, ...,\nu_k, \nu)-computable$ for numberings]\ \\
      A function $f: \subseteq M_1 \times \cdots \times M_k \rightarrow M$ is called $(\nu_1, ...,\nu_k, \nu)-computable$, iff $\exists$ computable $g: \NN^k \rightarrow \NN$ s.t. $f(\nu_1(i_1), ..., \nu_k(i_k)) = \nu \circ g(i_1, ..., i_k)$.\\
      \begin{tikzpicture}[>=stealth, ->, auto]
        \node (a) at (0, 0) { $\NN^k$ };
        \node (b) at (3, 0) { $\NN$ };
        \node (c) at (0,-3) { $M_1 \times \cdots \times M_k$ };
        \node (d) at (3,-3) { $M$ };
        \draw (a) -- (b) node [midway] {$g$};
        \draw (a) -- (c) node [midway, left] {$\nu_1,...,\nu_k$};
        \draw (c) -- (d) node [midway, below] {$f$};
        \draw (b) -- (d) node [midway] {$\nu$};
      \end{tikzpicture}
    \end{defi}
  }}
  \fbox{\parbox{\linewidth}{
    \begin{defi}[Notation]\ \\
      A $notation$ is a surjective function $\nu: \subseteq{\Sigma^*} \rightarrow M$.\\
    \end{defi}
    \begin{defi}[$(\nu_1, ...,\nu_k, \nu)-computable$ for notations]\ \\
      A function $f: \subseteq M_1 \times \cdots \times M_k \rightarrow M$ is called $(\nu_1, ...,\nu_k, \nu)-computable$, iff $\exists$ computable $g: {\Sigma^*}^k \rightarrow \Sigma^*$ s.t. $f(\nu_1(i_1), ..., \nu_k(i_k)) = \nu \circ g(i_1, ..., i_k)$.\\
      \begin{tikzpicture}[>=stealth, ->, auto]
        \node (a) at (0, 0) { ${\Sigma^*}^k$ };
        \node (b) at (3, 0) { $\Sigma^*$ };
        \node (c) at (0,-3) { $M_1 \times \cdots \times M_k$ };
        \node (d) at (3,-3) { $M$ };
        \draw (a) -- (b) node [midway] {$g$};
        \draw (a) -- (c) node [midway, left] {$\nu_1,...,\nu_k$};
        \draw (c) -- (d) node [midway, below] {$f$};
        \draw (b) -- (d) node [midway] {$\nu$};
      \end{tikzpicture}
    \end{defi}
  }}
  \fbox{\parbox{\linewidth}{
    \begin{defi}[Representation]\ \\
      A $representation$ is a surjective function $\delta: \subseteq{\Sigma^\omega} \rightarrow M$.\\
    \end{defi}
    \begin{defi}[$(\delta_1, ...,\delta_k, \delta)-computable$ for representations]\ \\
      A function $f: \subseteq M_1 \times \cdots \times M_k \rightarrow M$ is called $(\delta_1, ...,\delta_k, \delta)-computable$, iff $\exists$ computable $g: {\Sigma^\omega}^k \rightarrow \Sigma^\omega$ s.t. $f(\delta_1(i_1), ..., \delta_k(i_k)) = \delta \circ g(i_1, ..., i_k)$.\\
      \begin{tikzpicture}[>=stealth, ->, auto]
        \node (a) at (0, 0) { ${\Sigma^\omega}^k$ };
        \node (b) at (3, 0) { $\Sigma^\omega$ };
        \node (c) at (0,-3) { $M_1 \times \cdots \times M_k$ };
        \node (d) at (3,-3) { $M$ };
        \draw (a) -- (b) node [midway] {$g$};
        \draw (a) -- (c) node [midway, left] {$\delta_1,...,\delta_k$};
        \draw (c) -- (d) node [midway, below] {$f$};
        \draw (b) -- (d) node [midway] {$\delta$};
      \end{tikzpicture}
    \end{defi}
  }}

  \pagebreak

  \subsection{Recursive and recursively enumerable}\ \\
  There are two functions which classify automata into the two categories of deciders and recognizers (acceptors), which are defined as follows:\\
  \fbox{\parbox{\linewidth}{
    \begin{defi}[characteristic function]\ \\
      $cf_A(x) :=
      \begin{cases}
        \: 1, & \text{if $x \in A$}\\
        \: 0, & \text{otherwise}
      \end{cases}$
    \end{defi}
    \hrule
    \begin{defi}\ \\
      $df_A(x) :=
      \begin{cases}
        \: 1, & \text{if $x \in A$}\\
        \: div, & \text{otherwise}
      \end{cases}$
    \end{defi}
    Note that the authors of the course use "div" for diverging in the sense of non-terminating. Others may call the value "undefined".
  }}

  \vspace{10px}

  A set $A \subseteq \NN^k$ is called $recursive$ (decidable), iff its characteristic function $cf_A$ is computable, i.e., there exists a decider for $A$.\\
  \fbox{\parbox{\linewidth}{
    \begin{defi}
      $A \subseteq \NN^k \: recursive$
      \\
      $\Leftrightarrow cf_A : \NN^k \rightarrow \NN \: computable$
    \end{defi}
    \begin{theo}
      $A \subseteq \NN^k \: recursive$
      \\
      $\Leftrightarrow \exists \: computable \: f \in R^{(k)} \: s.t. \: A=f^{-1}\{0\}$
      \\
      I.e., all elements of $A$ are mapped to a fixed value (not necessarily 0) by a recursive function $f$.
    \end{theo}
    \hrule
    \begin{defi}
      $A \subseteq (\Sigma^*)^k \: recursive$
      \\
      $\Leftrightarrow A = f^{-1}\{\epsilon\} \: for \: some \: total \: computable \: f : (\Sigma^*)^k \rightarrow \Sigma^*$
    \end{defi}
  }}

  \pagebreak

  A set $A \subseteq \NN^k$ is called $recursively \; enumerable$ (semi-decidable), in short $r.e.$, iff $A$ is the domain of some computable function, i.e. there exists an acceptor for $A$.\\
  \fbox{\parbox{\linewidth}{
    \begin{defi}
      $A \subseteq \NN^k \: recursively \: enumerable$
      \\
      $\Leftrightarrow \exists \: computable \: f : \subseteq \NN^k \rightarrow \NN \: s.t. \: A = Dom(f)$
    \end{defi}
    \begin{theo}
      $A \subseteq \NN^k \: r.e.$
      \\
      $\Leftrightarrow df_A : \NN^k \rightarrow \NN \: computable$
    \end{theo}
    \begin{theo}
      $A \subseteq \NN^k \: r.e.$
      \\
      $\Leftrightarrow \pi^{(k)}[A] \: r.e.$
    \end{theo}
    \begin{theo}
      $A \subseteq \NN^k \: recursive$
      \\
      $\Leftrightarrow A \: r.e. \wedge \NN^k\backslash A \: r.e.$
    \end{theo}
    \begin{theo}[Projection Theorem]
      $A \subseteq \NN^k \: r.e.$
      \\
      $\Leftrightarrow \exists \: recursive \: B \subseteq \NN^{k+1} \: s.t. \: A = \{x \in \NN^k \: | \: (\exists t) \: (x, t) \in B\}$
    \end{theo}
    \hrule
    \begin{defi}
      $A \subseteq (\Sigma^*)^k \: r.e.$
      \\
      $\Leftrightarrow A = Dom(f) \: for \: some \: computable \: f : \subseteq (\Sigma^*)^k \rightarrow \Sigma^*$
    \end{defi}
  }}
  
  \newcommand{\redp}[2]{\: \textsc{#1} \leq_p \textsc{#2}}
  \newcommand{\linc}[2]{\: \textsc{#1} \in    \mathbf{#2}}
  
  \newpage
  \subsection{Hierarchies and separation}
  
    \begin{theo}[Time Hierarchy Theorem]\ \\
      $\mathbf{DTIME}\left(\oo{\frac{f(n)}{\log{f(n)}}}\right) \subsetneq \mathbf{DTIME}(f(n))$\\
    \end{theo}
%     \begin{proof}\ \\
%       $Let$
%     \end{proof}

    \begin{theo}[Cook-Levin\cite{cook71}]\ \\
%     \begin{theo}[Cook-Levin\cite{cook71,levin73}]\ \\
      $\linc{3SAT}{NP} \wedge (\forall \linc{L}{NP}) \redp{L}{3SAT}$
    \end{theo}


  \newpage

  A Wang tile\\
    \begin{tikzpicture}[scale=1.5]
      \tile{0}{0}{$c_{w_i}$}{$c_{e_i}$}{$c_{n_i}$}{$c_{s_i}$}
    \end{tikzpicture}

  Coloured Wang tiles\\
    \begin{tikzpicture}[scale=1.5]
      \wang{1}{1}{red}{green}{yellow}{orange}
      \wang{2}{1}{green}{red}{orange}{orange}
      \wang{3}{1}{red}{blue}{green}{yellow}
    \end{tikzpicture}

  Labeled Wang tiles\\
    \begin{tikzpicture}[scale=1.5]
      \tile{0}{0}{w}{e}{n}{s}
      \tile{1}{0}{e}{a}{n}{c}
      \tile{2}{0}{a}{b}{c}{d}
    \end{tikzpicture}

  Filling a grid with Wang tiles\\
    \begin{tikzpicture}[scale=1.5]
      \draw[help lines] (0,0) grid (5,3);
      \wang{1}{2}{red}{blue}{green}{yellow}
      \wang{0}{1}{green}{red}{orange}{orange}
      \wang{1}{1}{red}{green}{yellow}{orange}
      \wang{2}{1}{green}{red}{orange}{orange}
      \wang{3}{1}{red}{blue}{green}{yellow}
      \wang{2}{0}{green}{red}{orange}{orange}
      \wang{3}{0}{red}{green}{yellow}{orange}
      \wang{4}{0}{green}{red}{orange}{orange}
    \end{tikzpicture}

% \bibliography{1657+1658.bib}

\newpage
\begin{thebibliography}{9}

  \bibitem{cook71}
  Stephen A. Cook,
    \emph{The complexity of theorem-proving procedures}.
    Proceedings of the 3rd Annual ACM Symposuium on the Theory of Computing (STOC'71).
    ACM,
    New York 1971,
    pp 151–158.

\end{thebibliography}

\end{document}
