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

\title{INF2080\\Oblig 2}
\date{\textbf{Deadline:} February 23, 2018}

\setcounter{secnumdepth}{0}

\begin{document}

\maketitle

\section{Hand-in and deadline}
Hand in a single PDF file in \href{https://devilry.ifi.uio.no/}{Devilry}. Deadline is \textbf{February 23, at 23:59}.

\section{Problem 1: Pumping Lemma}
In the lecture, we saw that the language
\[
L=\{ab^nc^n\mid n\geq 0 \}\cup \{a^kw\mid k\neq 1, w\in\Sigma^* \text{
  does not start with an } a\}
\]

satisfies the pumping lemma for regular languages (Theorem 1.70 in the
book), yet we claimed that
this language was not regular. In this exercise you will complete this
proof.

\subsection{Problem 1a}
Use the pumping
lemma to show that the language

\[
  L_1=\{ab^nc^n\mid n\geq 0 \}
\]
is non-regular.

\emph{Hint: adapt pumping lemma examples seen in the lecture or book to language $L_1$.}
\subsection{Problem 1b}
Argue why $L$ must then be non-regular and explain why this is not a
counter-example to the pumnping lemma.

\section{Problem 2: Context-Free Languages}
Consider the language from Problem 1:
\[
  L_1=\{ab^nc^n\mid n\geq 0 \}
\]
\subsection{Problem 2a}
Construct a CFG that generates $L_1$.

\subsection{Problem 2b}
Sketch a state diagram for a PDA that recognizes $L_1$.

\end{document}