\documentclass{scrartcl}
\usepackage[margin=1in, left=0.5in, right=0.5in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fancyhdr}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD2} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[R]{5 octobre 2017}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\X}{\mathcal{X}}
\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{TD2 : Langages formels, calculabilité et complexité}

\begin{document}
\pagestyle{fancy}

\section{Arden's rule}
\begin{question}
Let ${\A}$, ${\B}$ be regular langages, prove that, if
$\epsilon\not\in {\A}$ then ${\X}=\mathcal{AX}\cup{\B}$ has a unique
language $\X$ solution. Express this solution in terms of $a$ (resp. $b$) a
regular expression recognizing ${\A}$ (resp. ${\B}$).

\textit{Advice:
\begin{enumerate}
\item find a first solution;
\item show that any solution is larger than your solution;
\item show that any solution is contained within your solution.
\end{enumerate}}
\end{question}

\section{Pumping lemma}

\begin{question}
  Justify whether or not the following languages are regular? 
  \begin{enumerate}
  \item $\{a^nb^n \mid n\in\mathbb{N}\}$
  \item $\{a^mb^n \mid n \equiv m \pmod d\}$ for a given $d\in\mathbb{N}$.
  \item $\{a^p \mid p \mbox{ premier }\}$
  \item $\{a^{P(n)} \mid n\in \mathbb{N}\}$ for a given $P\in \mathbb{N}[X]$.
  \end{enumerate}
\end{question}

\section{Puzzles}

\begin{question}
  Let $x$ and $y$ be two words such that $xy=yx$. What can you say
  about the shape of $x$ and $y$?
\end{question}

\begin{question}
  Let $(p,q)\in \mathbb{N}^*$, and $\mathcal{L}$ a regular language.
  When is $\dfrac{p}{q}\mathcal{L} = \left\{ u \mid \exists v:
  uv\in\mathcal{L}\mbox{ et } |u|=\dfrac{p}{q}|uv|\right\}$ also a
  regular language?
\end{question}


\section{Generalized Arden's rule}

\begin{defi}
  A monoid is an algebraic structure $(E,\bigodot,e)$ such that:
  \begin{itemize}
    \item[(binary operation)] For $x,y\in E^2$, $x\bigodot y\in E$
    \item[(associative)] For $x,y,z\in E^3$, $(x\bigodot y)\bigodot z=x\bigodot (y\bigodot z)$
    \item[(identity element)] For $x\in E$, $x\bigodot e=e\bigodot x = x$
  \end{itemize}
\end{defi}

\begin{defi}
  A semiring is an algebraic structure $(E,+,\times,0,1)$ such that:
  \begin{itemize}
  \item $(E,+,0)$ is a commutative monoid ($a+b=b+a$);
  \item $(E,\times,1)$ is a monoid;
  \item $\times$ is distributive over $+$ ($a\times (b+c)=a\times b + a \times c$ and $ (b+c)\times a=b\times a + c \times a$);
  \item $0$ is absorbing for $\times$ (i.e. $0\times a=a\times 0=0$)
  \end{itemize}
\end{defi}

\begin{question}
  Notice that $({\Ls},\cup,/,\emptyset,\epsilon)$ is a semiring where:
  \begin{itemize}
  \item ${\Ls}$ is the set of regular languages
    over $\Sigma$;
  \item $/$ is the concatenation $X/Y=\{xy \mid x\in X, y\in Y\}$;
  \item $\cup$ is the union;
  \item $\emptyset$ is the empty language;
  \item $\epsilon$ is the language containing only the empty word.
  \end{itemize}

  Let $(\Mn{},+,\times,0,1)$ be the set of square matrices of size $n$
  over the semiring $({\Ls},/,\cup,\emptyset,\epsilon)$ with
  \begin{itemize}
    \item $(M+N)_{i,j}=M_{i,j}\cup N_{i,j}$;
    \item $(M\times N)_{i,j}= \displaystyle{\bigcup_{1\leq k \leq n} M_{i,k} /  N_{k,j}}$;
    \item $0_{i,j}=\emptyset$
    \item $1_{i,j}=\begin{cases}\epsilon & i=j \\ \emptyset & \mbox{sinon} 
    \end{cases}$
    \item $M^* = \sum_{i\in\mathbb{N}} M^k$
  \end{itemize}

  Notice that $(\Mn,+,\times,0,1)$ is also a semiring.

  \textit{Remark: any semiring can be transformed into a semiring of matrices}
\end{question}

\begin{question}
  Let ${\A} \in \Mn$ with $\forall i,j ~ \epsilon \not\in A_{i,j}$ and
  ${\B}\in M_{n,1}({\Ls})$ a vector of size $n$, show that there is a
  unique solution to ${\X}\in M_{n,1}({\Ls})$ with
  ${\X}=\mathcal{AX^T}\cup {\B}$ (i.e. $\forall i: {\X}_i = \left(
  \bigcup_j ~ {\A}_{i,j} / {\X}_j \right) \cup {\B}_i$).
\end{question}

\begin{question}\emph{(Gaussian elimination)}
Given${\A}\in \Mn$ and ${\B}\in M_{n,1}({\Ls})$ show that when $n>1$
the languages $(\mathcal{A^*B})_i$ for $i\in \{1, \dots, n-1\}$ can be
expressed as $\mathcal{A'^*B'}_i$ for a given $\mathcal{A'}\in
M_{n}({\Ls}), {\B}'\in M_{n,1}({\Ls})$.
\end{question}

\begin{question}
Deduce an algorithm returning the regular expression corresponding to
a given automata.
\end{question}

\begin{question}
  What is the regular expression corresponding to:

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

\section{Monoid of a language}

\begin{defi}
Given an alphabet $\Sigma$ and a language $\mathcal{L}$ (not
necessarily regular) we state $\ml$ le syntactic morphism from
$\mathcal{L}$ defined as:
$\ml (u) = \{ (x,y) \in {\Sigma^*}^2 \mid xuy \in \Lc \}$.
\end{defi}

\begin{question}
  Show that $\ml$ is compatible with the concatenation, i.e.  $\forall
  u,v,w : \ml (v)=\ml (w) \Rightarrow \left( \ml(vu)=\ml(wu)\right)
  \land \left(\ml(uv)=\ml(uw)\right)$.
\end{question}

\begin{question}
  For each element $e\in\ml(\Sigma^*)$ we chose a an element $r(e)$
  tel que $\ml(r(e))=e$, and we define $u\odot v = \ml(r(u)) \odot
  \ml(r(v))=\ml(r(u)r(v))$.

  Justify that:
  \begin{itemize}
    \item $\odot$ does not depend on the choices for $r$.
    \item the structure $(\ml(\Sigma^*),\odot,\ml(\epsilon))$ induced
      by $\ml$ is a monoid
  \end{itemize}
and thus $\ml$ do is a morphism from the the free monoid over $\Sigma$
towards the monoid induced by $\ml$.

  \textit{Remark: any monoid $(M,\odot,e)$ compatible with a function
    $\mu$ induce a structure of monoid over $\mu(M)$}.
\end{question}

\begin{question}
  Prove that $\ml(\Sigma^*)$ is finite when $\Lc$ is regular.
\end{question}

\begin{question}
  Prove that when $\ml(\Sigma^*)$ is finite then $\Lc$ is regular.
\end{question}


\begin{question}
What does the the syntactic monoid of the well-parenthesed words looks like?
\end{question}

\end{document}
