\documentclass{scrartcl}
\usepackage[margin=1in, left=0.5in, right=0.5in]{geometry}
\usepackage[utf8]{inputenc}
%\usepackage[francais]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fancyhdr}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD1} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[R]{28 septembre 2017}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\usepackage{exsheets}[2014/09/14] % v0.16 or newer
\SetupExSheets{
  headings = runin ,
  headings-format = \large\bfseries\sffamily ,
  subtitle-format = \large\bfseries\sffamily ,
%  counter-within = section ,
%  counter-format = se.qu\IfQuestionSubtitleT{:} ,
%solution/print = true % uncomment for tutors
}

\usepackage{tikz}
\usetikzlibrary{automata,positioning}

\author{}
%\date{}
\title{TD1 : Langages formels, calculabilité et complexité}

\begin{document}
\pagestyle{fancy}

\section*{Find a deterministic tree automata for the following languages:}

\begin{question}
The words over the alphabet $\{a,b\}$ containing the factor $aab$ or
$aaab$.
\end{question}

\begin{question}
The words over the alphabet $\{a,b\}$ containing an even number of $a$
and an odd number of $b$.
\end{question}


\begin{question}
The words over the alphabet $\{a\}$ with a length that is a multiple of 3.
\end{question}

\begin{question}
For all $d\in\mathbb{N}$, the words over the alphabet $\{a\}$ with a
length that is a multiple of $d$.
\end{question}

\begin{question}
The binary representation of even integers. Integer are positive and
the numbers are given in the big-endian order (i.e. natural order:
101010 is 42).
\end{question}


\begin{question}
For all $d\in\mathbb{N}$, the binary representation of multiples of
$d$.
\end{question}

\begin{question}
For all $d\in\mathbb{N}$ the binary representation of numbers of the
numbers $c+k\times d$ for $k\in\mathbb{N}$.
\end{question}

\vspace{3em}

\section*{Given a regular language $\mathcal{L}$ prove that the following languages are also regular:}

\begin{question}
$Init(\mathcal{L}) = \{ u \mid \exists v : uv\in\mathcal{L}\}$
\end{question}

\begin{question}
$Min(\mathcal{L}) = \{ w\in\mathcal{L} \mid \not \not\exists u \in\mathcal{L} : u \mbox{ strict prefix of } w\}$
\end{question}

\begin{question}
$Max(\mathcal{L}) = \{ w \in\mathcal{L} \mid wu\in\mathcal{L}
  \Rightarrow u=\epsilon\}$
\end{question}

\begin{question}
$Cycle(\mathcal{L}) = \{ uv \mid vu \in \mathcal{L} \}$
\end{question}

\begin{question}
$\frac{1}{2}\mathcal{L} = \{ u \mid \exists v : uv \in \mathcal{L} \mbox{ and } |v|=|u|\}$
\end{question}

\end{document}
