\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}
\usepackage{mathtools}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD4} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[R]{19 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}}
\newcommand{\norm}[1]{\left\lvert#1\right\rvert}
\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}

\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}

\newcommand*\fo[1]{\tikz[baseline=(char.base)]{
                \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\usepackage{tikz}
\usetikzlibrary{automata,positioning}

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

\begin{document}
\pagestyle{fancy}


\section{Context-free grammars}


\begin{question}
  Give a context-free grammar for each of the following languages
  (don't justify too much):
  \begin{enumerate}
  \item $\Lc_0 = \{ a^ib^jc^k \mid i\neq j \lor j\neq k \}$
  \item $\Lc_1 =  \{ w \in \{a,b\}^* \mid \norm{w}_a \geq \norm{w}_b\}$
  \item $\Lc_2 = \{  w\in\{ (, ), 0, 1, *, +\} \mid w \mbox{ is a valid arithmetical expression}\}$
  \end{enumerate}
\end{question}

\begin{question}
There are several ways to parse valid arithmetical expression. Find a
non-ambiguous grammar where the parsing tree give the priority to $*$
over $+$ (i.e. $2+3*4$ is seen as the expression that equals $14$ and
not $20$).
\end{question}

\begin{question}
Show that the two grammars defined by $S$ and $Balanced$ recognize the
same language but one is ambiguous and not the other:
\[
\begin{array}{lcrclcr}
  Balanced & \rightarrow & (OneRight ~ Balanced \mid \epsilon & \hspace{10em} & S & \rightarrow &  SS \mid (S) \mid \epsilon\\
  OneRight & \rightarrow &  ) \mid  ( OneRight ~ OneRight \\
\end{array}
\]
\end{question}

\section{Context-sensitive grammars}

\begin{question}
Let us consider the following grammar:
\[ %
\begin{array}{rclcrcl}
S & \rightarrow & aSBC + aBC & \hspace{5em} & bB & \rightarrow & bb \\
CB & \rightarrow & BC &                     & bC & \rightarrow & bc \\
aB & \rightarrow & ab &                     & cC & \rightarrow & cc \\
\end{array}%
\]

What langage does it recognize ? Justify.
\end{question}

\begin{question}
Let us consider the following grammar:
\[ %
\begin{array}{rclcrcl}
S & \rightarrow & CD & \hspace{5em}         & Ab & \rightarrow & bA \\
 C & \rightarrow & aCA+bCB &                & Ba & \rightarrow & aB \\
AD & \rightarrow & aD &                     & Bb & \rightarrow & bB \\
BD & \rightarrow & bD &                     & C  & \rightarrow & \epsilon \\
Aa & \rightarrow & aA &                     & D & \rightarrow & \epsilon \\
\end{array}%
\]

What langage does it recognize ? Justify.
\end{question}

\begin{question}
Let us consider the following grammar:

\[ S\rightarrow aS+aSbS+\epsilon \]

What langage does it recognize ? Justify.

\end{question}

\section{Myhill -- Nerode}

Let $\Sigma$ be an alphabet and $\Ls$ a langage over this alphabet
(not necessarily regular).

\begin{defi}
Let $x,y\in {\Sigma^*}^2$ be two words, we define the following relation:

$$ x \sim_{\Ls} y ~~~\myeq~~~ \forall z\in\Sigma^* : xz\in\Ls \Leftrightarrow yz\in\Ls $$
\end{defi}

\begin{question}
  Show that $\sim_\Ls$ defines an equivalence relation (i.e. it is
  reflexive, symmetric and transitive).
\end{question}

\begin{question}
  Let $(x,y)\in{\Sigma^*}^2$ show that $x\sim_\Ls y$ implies
  $xc\sim_\Ls yc$ for all $c\in\Sigma$.
\end{question}

\begin{question}
  Show that if there is a finite number of equivalence classes for the
  relation $\sim_\Ls$ then $\Ls$ is regular.
\end{question}

\begin{question}
  Show that when $\Ls$ is regular then $\sim_\Ls$ has a finite number of
  equivalence classes.
\end{question}

\section{Myhill -- Nerode : applications}

\begin{defi}
  The left quotients of the free monoid induced by $\Ls$ are the
  equivalence classes of the relation $\sim_\Ls$.

  The left quotients of $\Ls$ are the $\Lc_w$ for $w\in\Sigma^*$ with
  $\Lc_w = \{ x \mid wx\in\Ls \}$. Notice there is a finite number of
  them since $x\sim_\Ls y \Leftrightarrow \Lc_x = \Lc_y$.
  \end{defi}

\begin{question}
  Find the left quotient and the minimal automaton for each of the
  following languages:
  \begin{itemize}
  \item $\Lc_3 = b(ba)^*$
  \item $\Lc_4 = \{ a^ib^j \mid i+j\mbox{ is even}\}$
  \item $\Lc_5 = \{ w\in\{a,b\}^* \mid w \mbox{ contains exactly once
    the factor } bb\}$
  \end{itemize}

\end{question}

\begin{solution}
  \begin{enumerate}
  \item Les classes sont $\emptyset$, $b(ba)^*$, $(ba)^*$, $a(ba)^*$
    on a donc

  \begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
    \node[state,initial] (q_1) {$b(ba)^*$};
    \node[state,right=of q_1] (q_0)   {$\emptyset$};
    \node[state,accepting] (q_2) [below=of q_1] {$(ba)^*$};
    \node[state](q_3) [right=of q_2] {$a(ba)^*$};
    \path[->]
    (q_1) edge  node {a} (q_0)
    (q_2) edge [bend left] node  {a} (q_0)
    (q_3) edge  node  {b} (q_0)
    (q_0) edge [loop above] node {a,b} ()
    (q_1) edge  node {b} (q_2)
    (q_2) edge [bend left] node {b} (q_3)
    (q_3) edge [bend left] node {a} (q_2);
    \end{tikzpicture}

\item les classes sont
  \fo{1} $\emptyset$,
  \fo{2} $\{ a^ib^j \mid i+j\mbox{ est pair}\}$,
  \fo{3} $\{ a^ib^j \mid i+j\mbox{ est impair}\}$,
  \fo{4} $\{ b^j \mid j\mbox{ est pair}\}$,
  \fo{5} $\{ b^j \mid j\mbox{ est impair}\}$ l'automate
  est donc~:

   \begin{tikzpicture}[shorten >=1pt,node distance=4cm,on grid,auto]
    \node[state,initial,accepting] (q_2) {2};
    \node[state, below=of q_2] (q_3) {3};
    \node[state, below right = 2cm and 2cm of q_1] (q_0)   {$\emptyset$};
    \node[state,accepting] (q_4) [right=of q_3] {4};
    \node[state](q_5) [right=of q_2] {5};
    \path[->]
    (q_5) edge [bend right] node {a} (q_0)
    (q_4) edge [bend left] node {a} (q_0)
    (q_2) edge  node {b} (q_5)
    (q_3) edge  node {b} (q_4)
    (q_4) edge [bend left] node {b} (q_5)
    (q_5) edge [bend left] node {b} (q_4)
    (q_2) edge [bend left] node {a} (q_3)
    (q_3) edge [bend left] node {a} (q_2);
    \end{tikzpicture}
      
    \item  les classes sont
  \fo{0} $\emptyset$,
  \fo{1} $(b?a)^*bb(ab?)^*$,
  \fo{2} $b(ab?)^* | a(b?a)^*bb(ab?)^*$,
  \fo{3} $(ab?)^*$,
  \fo{4} $b?(ab?)^*$,
  l'automate
  est donc~:\\
   \begin{tikzpicture}[shorten >=1pt,node distance=4cm,on grid,auto]
    \node[state,initial] (q_1) {1};
    \node[state, right=of q_1] (q_2) {2};
    \node[state, accepting, below=of q_2] (q_3) {3};
    \node[state, accepting, left=of q_3] (q_4) {4};
    \node[state, below right = 2cm and 2cm of q_1] (q_0)   {$\emptyset$};

    \path[->]
    (q_1) edge [bend left] node {b} (q_2)
    (q_2) edge [bend left] node {b} (q_3)
    (q_3) edge [bend right] node {b} (q_0)
    (q_1) edge [bend right] node {a} (q_0)
    (q_2) edge [bend right] node {a} (q_0)
    (q_3) edge [bend left] node {a} (q_4)
    (q_4) edge [bend left] node {b} (q_3)
    (q_4) edge [loop above] node {a} (q_4);
    \end{tikzpicture}
      
\end{enumerate}
\end{solution}

\end{document}
