\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]{TD3} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[R]{12 octobre 2017}
\newcommand{\A}{\mathcal{A}}
\newcommand{\Q}{\mathcal{Q}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\Ls}{{\mathcal{L}_\Sigma}}
\newcommand{\Lc}{{\mathcal{L}}}
\newcommand{\ml}{\mu_{\mathcal{L}}}
\newcommand{\Mn}{M_n(\Ls)}
\newcommand{\Vn}{{M_{n,1}(\Ls)}}
\newcommand{\td}{\tilde{\delta}}
\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
}
\newtheorem{defi}{Definition}

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

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

\begin{document}
\pagestyle{fancy}

\section{Are the following languages regular~? (Justify)}

\begin{question}
  $\Lc_0=\{ w\in\{a,b, c\}^* \mid (|w|_a=0) \Rightarrow (|w|_b=0)\}$
\end{question}

\begin{question}
  $\Lc_2=\{ w\in\{a,b\}^* \mid |w|_a< |w|_b \}$
\end{question}


\begin{question}
  $\Lc_1=\{ w\in\{a,b\}^* \mid 7 \mbox{ divide } |w|_a, 3 \mbox{
    divide } |w|_b, \}$
\end{question}


\begin{question}
  $\Lc_3=\{ w\in\{(,)\}^* \mid w \mbox{ is well-parenthesized} \}$
\end{question}


\section{Non equivalency of pumping lemmas}

Here are three version of the pumping lemma for a language $\Lc$~:
\[
\begin{array}{lrcl}
1)&\exists n\in \mathbb{N}, \forall u\in\Lc : |u|\geq n & \Rightarrow & \exists v,t,w \in \Sigma^* \hspace{1em} u=vtw \hspace{1em} |t|>0  \hspace{1em} \forall m\in\mathbb{N}\hspace{1em} vt^mw\in\Lc \\
2)&\exists n\in \mathbb{N}, \forall rus\in\Lc : |u|\geq n & \Rightarrow & \exists v,t,w \in \Sigma^* \hspace{1em} u=vtw \hspace{1em} |t|>0  \hspace{1em} \forall m\in\mathbb{N}\hspace{1em} rvt^mws\in\Lc \\
3)&\exists n\in \mathbb{N}, \forall ru_1\dots u_ns\in\Lc, |u_i|\geq 1 &\Rightarrow & \exists 1\leq i<j\leq n \hspace{1em} \forall m\in\mathbb{N}\hspace{1em} ru_1\dots u_{i-1}(u_i\dots u_j)^mu_{j+1}\dots u_ns \in\Lc \\
\end{array}
\]

\begin{question}
 Show that $\Lc=\{ w\in\{a,b\}^* \mid |w|_a = |w|_b \}$ satisfies
 lemma 1 but not lemma 2.
\end{question}


\begin{question}
 Show that $\Lc=\{ (ab)^n(cd)^n \mid n\in\mathbb{N} \}\cup \Sigma^*
  (aa+bb+cc+dd+ac+bd)\Sigma^* $ satisfy lemma 2 but not lemma 3.
\end{question}
  
\section{Brzozowski's algorithm}

Let $\Ls$ be a regular language over the alphabet $\Sigma$ and let
$\A=<\Q,\Sigma,\delta,i,\F>$ be a DFA recognizing the language 
$\Ls$ such that all the states of $\A$ are accessible from $i$.

\begin{question}
Show that $Rev(\Ls)=\{ a_n \dots a_1 \mid a_1\dots a_n \in\Ls \}$ is
recognized by the NFA $Rev(\A)=<\Q,\Sigma,\delta',\F,\{i\}>$ where
$\delta'(q,c)=v \Leftrightarrow \delta(v,c)=q$.
\end{question}

\begin{defi}
Given an NFA $\B=<\Q_\B,\Sigma,\delta_\B,\I_\B,\F_\B>$ we note
$Det(\B)$ the DFA obtained by powerset construction of $\B$, We recall
$Det(\A)=<2^{\Q_\B},\Sigma,2^{\delta_\B},\I_\B,\{ q\in2^{\Q_\B} \mid
q\cap \F_\B\neq\emptyset\}>$) with $2^{\delta_\B}(e,v)=\{\bigcup_{q\in
  e}\delta_\B(q,v)\}$.
\end{defi}

\begin{question}
\label{lem:det}
Show that ofr $Det(B)=<2^\Q_\B,\Sigma,2^{\delta_\B},\I_\B,\{
q\in2^{\Q_\B} \mid q\cap \F_\B\neq\emptyset\}>$ we have the
equivalency between $q\in \tilde{2^{\delta_\B}}(\I_\B,w_1\dots w_n)$
and the existence of $q_1, \dots ,q_n,q_{n+1}$ such that
$q_1\in\I_\B$, $q_{n+1}=q$ et $q_{i+1}\in \delta_\B(q_i,w_i)$.
\end{question}


\begin{defi}
$leftEquiv(x,y) = \forall z : (zx\in\Ls)\Rightarrow (zy\in\Ls)$ 
\end{defi}

\begin{question}
Let $Det(Rev(\Ls))=<\Q_d,\Sigma,\delta_d,i_d,\F_d>$. Show that for all
$x,y\in (\Sigma^*)^2$ we have: $$LeftEquiv(x,y) \Rightarrow (
\tilde{\delta_d}(i_d,x)=\tilde{\delta_d}(i_d,y) )$$
\end{question}

\begin{question}
Deduce from the Myhill--Nerode theorem that $Det(Rev(\Ls))$ is a minimal
automaton recognizing $Rev(\Ls)$.

\emph{We recall the Myhill--Nerode theorem. Given ax language $\Lc$ we
  consider the relation of equivalence $RightEquiv(x,y) = \forall z:
  xz \in Lc \Leftrightarrow yz \in \Lc$. The Myhill--Nerode theorem
  states that any DFA recognizing $\Ls$ contains at least as many
  states as the number of equivalence classes of $RightEquiv$}
\end{question}

\begin{question}
Deduce an algorithm to compute the minimal automaton recognizing $\Ls$.
\end{question}

\begin{question}
What is the complexity of this algorithm?
\end{question}

\end{document}
