\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:} April 1, 2025}

\setcounter{secnumdepth}{0}

\begin{document}

\maketitle

\section{Hand-in and deadline}
Hand in a single PDF file containing your answers to all 3 Problems \href{https://devilry.ifi.uio.no/}{Devilry}. The deadline is \textbf{April 1, 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}

\subsection{Problem 3a}

Draw a state diagram for a Turing machine 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}\}$

\subsection{Problem 3b}

Give an implementation-level description of a Turing machine 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}\}$.

An example of an ``implementation-level description'' is Sipser's Example 3.7, which decides the language $\{0^{2^{n}} \mid n \geq 0\}$:
\begin{quote}
  On input string w:
  \begin{enumerate}
    \item Sweep left to right across the tape, crossing off every other 0
    \item If in stage 1 the tape contained a single 0, accept
    \item If in stage 1 the tape contained an odd number of 0s, reject
    \item Return the head to the start of the tape
    \item Go to stage 1
  \end{enumerate}
\end{quote}

If you would like to play around and test your Turing machines, a Turing machine simulator is available at \url{https://github.com/torenord/universaltm}.
It runs Turing Machines from a text file in the format specified in the \texttt{README}.
% 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.

\end{document}\grid
\grid
