Calculability and Computability - Practicing

Quelques exercices d'entrainement.

Exercices

Exercice

  • Question

    Pour chacun des langages suivants dire s'il est régulier et dans ce cas construire un automate minimum :

    • \(L = \{a^p b^q, p \in N, q \in N \}\)
    • \( L = \{a^p b^q, p > q \}\)
    • \( L = \{a^p b^q, p \geq p_0, q \geq q_0 \}\) (\(p_0,q_0\) étant fixés).
  • Question

    Soit L un langage régulier, dire si les langages suivants sont aussi réguliers pour \(\alpha \in V^\star\) :

    • \(L_1 = D_L(\alpha)\)
    • \(L_2(\alpha) = \{ \beta \mid \beta \in L \text{ et } \alpha \text{ facteur gauche de } \beta \}\).

Exercice

Soit le langage \(L\) des mots de la forme \( ac^{i_1}ac^{i_2}...ac^{i_k}\) avec \( k > 0 \) et tels qu'il existe une partition \(A\), \(B\) de \(\{ 1,2,..,k\}\) avec \( \sum_{p \in A} i_p = \sum_{p \in B} i_p \).

  • Question

    Construire une machine de Turing qui reconnait \(L\).

Exercice

Montrer que les langages suivants ne sont pas réguliers.

  • Question

    \(L_1 = \{ w w^R: w \in {a,b }^\star \}\) où \(w^R\) représente l'inversion de \(w\).

  • Question

    \(L_2 = \{ w w : w \in {a,b }^\star \}\)

  • Question

    \(L_3 = \{ w w[a \mapsto b, b \mapsto a ] : w \in {a,b }^\star \}\) où \( w[a \mapsto b, b \mapsto a ]\) est le mot \(w\) dans lequel les occurences de \(a\) ont été remplacées par \(b\) et celles de \(b\) par \(a\) et ceci de manière simultanée.

Exercice

  • Question

    Est-il vrai ou faux que tout sous-ensemble d'un langage régulier est régulier? Justifier votre réponse.

Exercice

  • Question

    Montrer que le langage suivant n'est pas régulier: \[L = \{ a^{n}b^{14} a^{m}b^{18} a^{n+m}: n,m \geq 1 \}\]

Exercice

  • Question

    Montrer que les deux langages suivants sur \(\{a,b\}\) ne sont pas réguliers:

    1. \({\cal L}_1 = \{ a^{n!} : n \in Nat \}\)
    2. \({\cal L}_2 = \{ a^n b^n a^n : n \in Nat \}\)

Exercice

  • Question
    1. Montrer que \(\mathcal{L}_3 = \{ a^n: n \ n'est \ pas \ premier \}\) satisfait le lemme de pompage des langages réguliers.
    2. Montrer que \(\mathcal{L}_3\) n'est pas régulier.
    3. Conclure.

Exercice

Commenter les affirmations suivantes en les justifiant ou en les réfutant.

  1. Tout sous-ensemble d'un langage régulier est régulier.
  2. Soit \(\mathcal{L}\) une famille de langages réguliers sur \(\Sigma\): \(\mathcal{L} = \{ \mathcal{L}_i : i \in I \}\) où \(\mathcal{L}_i\) est régulier et \(I\) est un ensemble d'indexes. Alors \(\bigunion_{i \in I}{\mathcal{L}_i}\) est régulier.
  3. \(\{ xyx^R : x,y \in \Sigma^*\}\) est régulier ou \(x^R\) est le mot \(x\) inversé.

Exercice

  • Question

    Montrer que le langage \(\mathcal{L}_4 = \{ www : w \in \{a,b\}^*\}\) n'est pas régulier.

Exercice

  • Question

    Construire une machine de Turing \(M\) calculant la fonction suivante: \[\forall w \in \Sigma^{\star} : f(w) = w w^R\] La construction s'appuiera sur une justification mathématique de la preuve d'adéquation de la machine M à la spécification.

Exercice

  • Question

    Construire un DFA acceptant le langage \(L \subseteq \{a,b\}^{\star}\) contenant tous les mots et uniquement les mots \(x\) qui satisfont simultanément les 3 conditions suivantes:

    1. la longueur de \(x\) est divisible par 3,
    2. \(x\) commence par \(a\) et termine par \(b\),
    3. \(aaa\) n'est pas un sous-mot de \(x\).

Exercice

  • Question

    Étant donné le NFA suivant M:

    \begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,%
        position/.style args={#1 degrees from #2}{at=(#2.#1), anchor=#1+180, shift=(#1:2cm)}%
    ]
    \node[state,initial above] (q_0)   {$q_0$};
    \node[left=0cm and 4cm of q_0](c_1) {};
    \node[right=0cm and 4cm of q_0](c_2) {};
    
    \foreach \i/\f [evaluate=\i as \a using -72+72*\i] in {1/accepting, 2/accepting, 3/accepting, 4/accepting, 5/}
      \node[state,\f,position={\a} degrees from c_1] (q_\i) {$q_\i$};
    
      \foreach \i/\f [evaluate=\i as \a using 180+51.4*6 - 51.4*\i] in {6/accepting, 7/accepting, 8/accepting, 9/accepting, 10/accepting, 11/accepting, 12/}
      \node[state,\f,position={\a} degrees from c_2] (q_\i) {$q_{\i}$};
    
      \path[-latex]
        (q_0) edge node {a} (q_1)
        (q_1) edge node {a} (q_2)
        (q_2) edge node {a} (q_3)
        (q_3) edge node {a} (q_4)
        (q_4) edge node {a} (q_5)
        (q_5) edge node {a} (q_1)
    
        (q_0) edge node {a} (q_6)
        (q_6) edge node {a} (q_7)
        (q_7) edge node {a} (q_8)
        (q_8) edge node {a} (q_9)
        (q_9) edge node {a} (q_10)
        (q_10) edge node {a} (q_11)
        (q_11) edge node {a} (q_12)
        (q_12) edge node {a} (q_6);
    \end{tikzpicture}
    

    construire un DFA M' équivalent à M ne possédant que des états atteignables.

Exercice

  • Question

    Montrer que les langages suivants sur \(\Sigma = \{0,1\}\) sont réguliers:

    1. tous les mots de longueur 2;
    2. tous les mots contenant au moins une fois la lettre \(0\);
    3. tous les mots ne contenant pas plus que deux \(0\) consécutifs.

    Remarque : on pourra donner des expressions régulières décrivant ces langages.

Exercice

Soit \(\Sigma = \{r,l,u,d\}\) l'ensemble de quatre symboles représentant chacun un déplacement élémentaire sur un quadrillage. A tout mot sur \(\Sigma^{\star}\), on associe un chemin du quadrillage. Ainsi, au mot \(ddhghd\) correspond le chemin suivant:

\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,
dot/.style={circle,fill,inner sep=2pt}]
\node [dot] (n_0);
\node [dot,right=of n_0] (n_1);
\node [dot,right=of n_1] (n_2);
\node [dot,above=of n_2] (n_3);
\node [dot,left=of n_3] (n_4);
\node [dot,above=of n_4] (n_5);
\node [dot,right=of n_5] (n_6);
\node [dot,right=of n_6] (n_7);
\node [dot,below=of n_7] (n_8);
\path[-latex]
    (n_0) edge node {r} (n_1)
  (n_1) edge node {r} (n_2)
  (n_2) edge node {u} (n_3)
  (n_3) edge node {l} (n_4)
  (n_4) edge node {u} (n_5)
  (n_5) edge node {r} (n_6)
  (n_6) edge node {r} (n_7)
  (n_7) edge node {d} (n_8);

\end{tikzpicture}

Soit \(L\) le langage des mots sur \(\Sigma^{\star}\) correspondant aux chemins qui reviennent au point de départ.

  • Question

    Définir \(L\) par des conditions de comptage approprié de lettres.

  • Question

    En utilisant le théorème du gonflement pour les langages algébriques, montrer que \(L\) n'est pas à contexte libre (Trouver un mot particulier de longueur suffisante et montrer qu'il ne satisfait pas aux conditions du théorème).

Exercice

Soit le langage \(L \subseteq \{a,b\}^{\star}\) composé de tous les mots comprenant un nombre impair de \(a\) et un nombre pair de \(b\).

  • Question

    [2013-10-10 jeu. 17:53] Construire un DFA \(M\) qui accepte \(L\) et prouver que \(L = L(M)\).

Exercice

  • Question

    Commenter les affirmations suivantes en les justifiant ou en les réfutant.

    1. Tout sous-ensemble d'un langage régulier est régulier.
    2. \(\{ xx^R : x,y \in \Sigma^*\}\) est régulier où \(x^R\) est le mot \(x\) inversé.
    3. \(\{a^i b^j : 1 \leq i \leq j \}\) est régulier.

Exercice

On rappelle le lemme de pompage pour les langages algébriques :

Si \(L\) est un langage algébrique, alors il existe une constante \(N\) telle que pour tout mot \(z \in L\), si \(|z| > N\), alors on peut écrire \(z = uvwxy\) avec \(|vx| \geq 1\), \(|vwx| \leq N\) et \(\forall \; n \geq 0 \quad uv^nwx^ny \in L\).

  • Question

    En utilisant le lemme de pompage, montrer que l'ensemble des mots sur \(\{0,1\}\) qui représentent l'écriture binaire d'un nombre premier n'est pas algébrique.

    Indication : considérer un mot \(w = uv^pwx^py\) avec \(p\) premier. On rapelle que les nombres premiers sont en nombre infini et que \(2^{p-1}-1 \equiv 0 \pmod{p}\) ( petit théorème de Fermat ).

Exercice

Soit le dispositif suivant :

Sorry, your browser does not support SVG.

Une bille est lâchée en \(A\) ou en \(B\). Les leviers \(x_1\), \(x_2\) et \(x_3\) orientent la bille vers la gauche ou la droite. Chaque fois que la bille heurte un levier, le levier change d'orientation, de telle sorte que la bille suivante qui rencontre le même levier prendra la branche opposée.

  • Question

    Modéliser ce dispositif par un automate à états finis. On pourra dénoter une bille en \(A\) par la lettre \(0\) et une bille en \(B\) par la lettre \(1\). Une séquence de \(\{0,1\}^{\star}\) sera acceptée si la dernière bille sort en \(D\).

  • Question

    Décrire l'ensemble accepté par l'automate par des conditions appropriées sur le mot d'entrée.

Exercice

  • Question

    Construire une machine de Turing qui, pour \(n \in {\mathbb N}\), calcule la fonction \(\lceil\log_2 n \rceil\). On rappelle que \(\lceil n \rceil\) désigne le plus petit entier plus grand que \(n\).

    On pourra supposer l'existence d'une machine de Turing énumérant les entiers à partir de 0 et l'utiliser comme procédure.

Exercice

  • Question

    Construire une machine de Turing reconnaissant le langage des palindrômes.

  • Question

    Construire une machine de Turing calculant \(n+1\) pour \(n\) donné. Le nombre \(n\) sera représenté en binaire.

  • Question

    Donner explicitement la table d'une machine de Turing qui décide si un mot \(w \in \{0, 1\}^{\star}\) contient au moins autant de \(0\) que de \(1\). On prendra soin de démontrer que la machine fait bien ce qu'elle est censée faire.

Exercice

Le problème des « busy beavers » (en français : « castors affairés ») a été introduit par Radó, dans le but de définir « simplement » une fonction non calculable. Le modèle de machines de Turing considéré est le suivant : on suppose les machines déterministes, possédant un ruban bi-infini, un alphabet de ruban réduit à \(\Gamma = \{1, B\}\). On suppose de plus que les machines possèdent un unique état final, duquel aucune transition ne sort, et qui n’est pas compté parmi les états de la machine. Enfin, on considèrera toujours un ruban initialement complètement blanc, i.e. que la machine démarre toujours sur \(\epsilon\). Soit \(E_n\) l'ensemble des machines de Turing vérifiant ces conditions et possédant \(n\) états.

La fonction de Radó, notée \(Σ(n)\), est définie comme le nombre maximum de \(1\) écrits sur la bande (pas nécessairement consécutifs) après qu’une machine de \(E_n\) s’est arrêtée : \[\Sigma(n) = \max\{f(M) \mid M \in E_n \}. \]

  • Question

    Justifier l'existence de \(\Sigma(n)\) pour tout \(n \geq 1\).

  • Question

    Calculer \(\Sigma(1)\) et \(\Sigma(2)\).

  • Question

    Montrer que \(\Sigma(3) \geq 6\) (borne en fait optimale).

  • Question

    Montrer que la fonction \(\Sigma\) est strictement croissante.

    Le modèle de fonction calculable considéré est le suivant : \(f\) est calculable si et seulement si il existe une machine de Turing qui, sur un ruban contenant initialement \(n\) symboles \(1\) consécutifs à droite du symbole blanc de départ, s’arrête après un nombre fini de déplacements en produisant un bloc de \(f(n)\) symboles 1 consécutifs.

  • Question

    Soit \(f\) une fonction calculable par une MT à \(k\) états. Montrer que \(f(n) ≤ Σ(k + n)\).

  • Question

    Montrer que la fonction de Radó n’est pas calculable.