\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 1}
\author{IN2080}
\date{\textbf{Deadline:} February 11, 2022}

\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}. The deadline is \textbf{February 11, 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: Regular languages}
Let $A$ and $B$ be regular languages defined by DFAs $\mathcal A$ and
$\mathcal B$. Let $n_\mathcal A$ and $n_\mathcal B$ be the number of
states in $\mathcal A$ and $\mathcal B$, respectively.

\subsection{Problem 1a}
What are the worst-case (highest) number of states in \textbf{DFAs} for the languages $A\cap B$ and $A^*$?

\subsection{Problem 1b}
What are the worst-case (highest) number of states in \textbf{NFAs} for the languages $A\cap B$, $AB$ and $A^*$?

\subsection{Problem 1c}
Create a regular expression defining the same language as the NFA

\begin{center}
    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
                        semithick]

        \node[initial,state] (q0) {$q_0$};
        \node[state] (q1) [above of=q0] {$q_1$};
        \node[state,accepting] (q2) [right of=q0] {$q_2$};
        \node[state] (q3) [above of=q2] {$q_3$};

        \path (q0) edge [bend left] node {$a$} (q1)
                    edge node {$b$} (q2)
                (q1) edge [loop above] node {$a$} (q1)
                    edge [bend left] node {$a$} (q0)
                (q2) edge [bend left] node {$c$} (q3)
                (q3) edge [loop above] node {$c$} (q3)
                    edge [bend left] node {$c$} (q2);
    \end{tikzpicture}
\end{center}

\subsection{Problem 1d}
Create a DFA for the language
\begin{align*}
    \{w\mid \text{$w$ contains equally many occurrences of the substrings 01 and 10}\}.
\end{align*}

\section{Problem 2: all-NFAs}
An all-NFA is defined in Sipser, problem 1.43 as a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ that accepts $x\in\Sigma^*$ if \emph{every} possible state that $M$ could reach after reading input $x$ is in $F$ (as opposed to \emph{at least one}).

If any branch in an all-NFA computation reaches an implicit or explicit sink state, the input is not accepted.

Show how an all-NFA can be converted to an equivalent DFA.

\emph{Hint: Adjust the conversion from NFA to DFA shown in the lectures.}


\end{document}\grid
\grid
