\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[colorlinks=true]{hyperref}
\usepackage{parskip}
\usepackage{tikz}
\usetikzlibrary{arrows,automata}

\title{Oblig 2}
\author{IN2080}
\date{\textbf{Deadline:} March 20, 2020}

\setcounter{secnumdepth}{0}

\begin{document}

\maketitle

\section{Hand-in and deadline}
Hand in a single PDF file (containing your answers to Problems 1 and 2) and 3 text files (containing your answers to Problem 3) in \href{https://devilry.ifi.uio.no/}{Devilry}. The deadline is \textbf{March 20, at 23:59}.

We recommend \LaTeX{}, but all major text editors allows exporting to PDF. You can get help with \LaTeX{} at the group sessions. You can also download the \LaTeX{} source (\texttt{.tex}) for this assignment at the assignments page.

\section{Problem 1: Context-free languages}

Consider the languages
\[
L_1 = \{\mathsf{a}\mathsf{b}^n\mathsf{c}^n \mid n \geq 0\}
\]
and
\[
L_2 = \{\mathsf{a}^i\mathsf{b}^j\mathsf{c}^k \mid i, j, k \geq 0 \text{ and } i + j = k\}.
\]


\subsection{Problem 1a}

Construct a CFG which generates $L_1$.

\subsection{Problem 1b}

Give the state diagram for a PDA which recognizes $L_1$.

\subsection{Problem 1c}

Show that $L_2$ is context-free.


\section{Problem 2: Pumping lemmas}

\subsection{Problem 2a}
Consider the language $L_2$ from problem 1. Prove, using the pumping lemma for regular languages, that $L_2$ is not regular.

\subsection{Problem 2b}
Let $L_3 = \{\mathsf{a}^i\mathsf{b}^j\mathsf{c}^k \mid i, j, k \geq 0 \text{ and } i \times j = k\}$.

Prove, using the pumping lemma for context-free languages, that $L_3$ is not context-free.

\section{Problem 3: Turing machines}

In this problem you will give implementations of Turing machines using the Turing machine simulator found on \url{https://github.com/torenord/universaltm} and following the format specified there. Hand in one text file for each problem, giving your description of the specific Turing machine, which can be run using that simulator.

\subsection{Problem 3a}

Create a Turing machine $M_1$ deciding the language from chapter 3: $\{w\#w \mid w \in \{0, 1\}^*\}$. Deliver a text file named \textsf{M1.txt} containing the description of the Turing machine.

\subsection{Problem 3b}

Create a Turing machine $M_{3.8a}$ deciding the language from exercise 3.8a: $\{w \in \{0, 1\}^* \mid w \text{ contains an equal number of \textsf{0}s and \textsf{1}s}\}$. Deliver a text file named \textsf{M3-8a.txt} containing the description of the Turing machine.

\subsection{Problem 3c}

Create a Turing machine $M_{3.8b}$ deciding the language from exercise 3.8b: $\{w \in \{0, 1\}^* \mid w \text{ contains twice as many \textsf{0}s as \textsf{1}s}\}$. Deliver a text file named \textsf{M3-8b.txt} containing the description of the Turing machine.

\end{document}\grid
\grid
