\documentclass[a4paper]{article}
\usepackage{entete}
\title{Langage de pile d'un automate à pile}
\date{}

\begin{document}
\maketitle
\begin{thm}
    On considère un automate à pile $\mathcal A = (\Sigma,\Gamma,Q,\delta,\gamma_0,F)$.

    Soit $H=\{\gamma \in \Gamma^*~|~ \exists f \in \Sigma^*,~ \exists q\in Q,~ (q_0,\gamma_0)\xrightarrow[]{f}(q,\gamma)\}$ le langage de pile de $\mathcal A$.

    Alors $H$ est rationnel.
\end{thm} 

\begin{proof}
    On pose $A_n = \{a_1,\ldots,a_n,\overline{a_1},\ldots,\overline{a_n}\}$ et on définit une relation $\to$ sur $A_n^*$ par~:
    $$w\to w' \Leftrightarrow \exists i,~\exists u,v \in A_n^*,~w=ua_i\overline{a_i}v \text{ et } w' = uv.$$
    On remarque que la relation $\to$ est noetherienne (il n'y a pas de chaîne infinie, car la longueur des mots est strictement décroissante), et confluente (si $x\to^* y$ et $x \to^* y'$, alors il existe $z$ tel que $y\to^*z$ et $y' \to^* z$).

    Donc pour tout $w$, il existe un unique mot $\rho(w)$ minimal pour $\to$.

    On a alors le lemme~:
    \begin{lem}
        $$\{w~|~\rho(w)=\varepsilon\} = D_n^*.$$
    \end{lem}

    \begin{prooflem}
        \begin{itemize}
            \item["$\subseteq$"~:] Soit $w$ tel que $\rho(w)=\varepsilon$, et soit $k$ tel que $w\to^k \varepsilon $.
            
            Si $k=0$, alors $w=\varepsilon$ et donc $w\in D_n^*$.

            Soit $k\in\N$ tel que pour tout $w$, $w\to^k \varepsilon ~\Rightarrow w\in D_n^*$.
            Soit $w$ tel que $w\to^{k+1} \varepsilon$. Alors il existe $w'$ de la forme $uv$ de taille $2k$ tel que $w'\to^k \varepsilon$, et tel que $w = ua_i\overline{a_i}v$. Alors $w \in D_n^*$.

            \item["$\supseteq$"~:] Évident par définition de $\to$ (une récurrence sur la longueur convaincra les sceptiques). 
        \end{itemize}
    \end{prooflem}

    On définit maintenant la substitution $\sigma$ sur $A_n^*$ par $\sigma(a) = D_n^* a D_n^*$.

    On a alors le lemme~:
    \begin{lem}
        Pour tout $w\in A_n^*$, $$\sigma(w) = \{w'~|~w'\to^* w\}.$$
    \end{lem}

    \begin{prooflem}
        \begin{itemize}
            \item["$\subseteq$"~:] Soit $w=w_1\ldots w_k$. Alors $\sigma(w) = D_n^* w_1 D_n^*\ldots D_n^* w_k D_n*$. 

            Soit $w' \in \sigma(w)$. Alors, par le lemme précédent, $w' \to^* w$.

            \item["$\supseteq$"~:] Par récurrence sur la longueur de la réduction $w' \to^p w$~:

            Le cas $p=0$ est trivial.

            Soit $p$ tel que tout mot $w'$ vérifiant $w'\to^p w$ soit dans $\sigma(w)$. Soit $w'$ tel que $w' \to^{p+1} w$.

            Alors il existe $\hat w$ vérifiant 
            \begin{itemize}
                \item $w' \to \hat w$
                \item $\hat w \to^p w$
                \item $\hat w = uv$
                \item $w' = ua_i\overline{a_i}v$
            \end{itemize}
            Par hypothèse de récurrence, $\hat w$ est de la forme $d_1w_1\ldots d_kw_k d_{k+1}$, avec les $d_i$ dans $D_n^*$.

            Alors $u$ est de la forme $d_1w_1\ldots d_j$ (resp. $d_1w_1\ldots d_jw_j$) et $v$ de la forme $w_j\ldots w_kd_{k+1}$ (resp. $d_{j+1} \ldots w_k d_{k+1}$).

            $w'$ est donc de la forme \\$d_1w_1\ldots d_j a_i\overline{a_i} w_j \ldots w_kd_{k+1}$ (resp. $d_1w_1 \ldots d_j w_j a_i\overline{a_i} d_{j+1}\ldots w_k d_{k+1}$), ce qui conclut la récurrence car $d_j a_i\overline{a_i}$ (resp. $a_i\overline{a_i} d_{j+1}$) est dans $D_n^*$.
        \end{itemize}
    \end{prooflem}

    \begin{lem}
        Pour tout rationnel $K$ sur $A_n^*$, le langage $\rho(K) = \{\rho(w)~|~w\in K\}$ est rationnel.
    \end{lem}

    \begin{prooflem}
        Un mot $w$ est dans $\rho(K)$ si et seulement si il est irréductible pour $\to$, et si il existe $w'\in K$, tel que $w'\to^*w$.

        Donc 
        $$\rho(K) = \sigma^{-1}(K) ~\backslash~ \left( \sum_{i=1}^n A_n^* a_i \overline{a_i} A_n^* \right) .$$
        Par stabilité des langages rationnels, $\rho(K)$ est rationnel.
    \end{prooflem}


    On va maintenant montrer que le miroir $\tilde H$ de $H$ est rationnel, ce qui impliquera que $H$ est rationnel.

    On suppose que dans l'automate $\mathcal A$, l'alphabet de pile est $\Gamma=\{a_1,\ldots,a_n\}$.

    Pour une transition $\tau = q,\gamma \xrightarrow{y} q',h$ dans $\mathcal A$, on définit $\mu(\tau) = \overline \gamma \tilde h$, que l'on étend à $\delta^*$.

    On dit que deux transitions $\tau$ et $\tau'$ sont {\em consécutives} si l'état d'arrivée de $\tau$ est le même que l'état de départ de $\tau'$.

    On appelle $K$ l'ensemble des suites de transitions de $\mathcal A$ consécutives.

    $K$ est clairement rationnel, car reconnu par l'automate $\mathcal A$ auquel on enlève la pile.

    On a alors 
    $$\tilde H = \rho(\gamma_0 \mu(K)) \cap \Gamma^*.$$

    Par le lemme précédent, et stabilité des langages rationnels, $\tilde H$ est rationnel.

    
    
\end{proof}

Références~: Carton, Langages formels, calculabilité et complexité.

Leçons : 909, 911



\end{document}
