Théorie des langages : Td 2 automate finis
Télécharger PDFExercices sur les Grammaires et Langages Formels (Licence 2)
Exercice 1
Soit \( V_T = \{a, b, c, d\} \). Donner une grammaire \( G = (V_T, V_N, S, R) \) qui génère le langage \( L = \{cc^*bd, a(ba)^*bcc^*ab\} \).
\( V_N = \{S, C, B\} \)
\( R = \{ S \rightarrow cCbd \mid aBbcCab; C \rightarrow cC \mid \epsilon; B \rightarrow baB \mid \epsilon \} \)
Exercice 2
Soit \( V_T = \{a_1, a_2, \dots, a_n\} \). Donner une grammaire \( G = (V_T, V_N, S, R) \) qui engendre le langage \( V_T^* \).
\( V_N = \{S, A\} \)
\( R = \{ S \rightarrow AS \mid \epsilon; A \rightarrow a_1 \mid a_2 \mid \dots \mid a_n \} \)
Exercice 3
Donner une grammaire qui engendre chacun des langages suivants :
a) \( L_1 = \{ w \in \{a, b, c\}^* \mid w \) contient au moins une occurrence de la lettre 'a' \}
Soit \( G_1 = (V_T, V_N, S, R) \), où :
\( V_T = \{a, b, c\} \)
\( V_N = \{S, A\} \)
\( R = \{ S \rightarrow AaA; A \rightarrow aA \mid bA \mid cA \mid \epsilon \} \)
b) \( L_2 = \{ w \in \{a, b\}^* \mid w = a^n b^m a \) ou \( w = ba^n; n, m \geq 1 \} \)
Soit \( G_2 = (V_T, V_N, S, R) \), où :
\( V_T = \{a, b\} \)
\( V_N = \{S, A, B\} \)
\( R = \{ S \rightarrow ABa \mid bA; A \rightarrow aA \mid a; B \rightarrow bbB \mid b \} \)
c) \( L_3 = \{ w \in \{0, 1\}^* \mid w = 1(101)^n 00 \) ou \( w = 0(010)^n 11; n \geq 0 \} \)
Soit \( G_3 = (V_T, V_N, S, R) \), où :
\( V_T = \{0, 1\} \)
\( V_N = \{S, A, B\} \)
\( R = \{ S \rightarrow 1A \mid 0B; A \rightarrow 101A \mid \epsilon; B \rightarrow 010B \mid \epsilon \} \)
d) \( L_4 = \{ w \in \{0, 1\}^* \mid w \) a un nombre de 1 égal au nombre de 0 \}
Soit \( G_4 = (V_T, V_N, S, R) \), où :
\( V_T = \{0, 1\} \)
\( V_N = \{S\} \)
\( R = \{ S \rightarrow S0S1 \mid S1S0 \mid \epsilon \} \)
e) \( L_5 = \{ w \in \{0, 1\}^* \mid w \) ne contient pas de 0 consécutifs \}
Soit \( G_5 = (V_T, V_N, S, R) \), où :
\( V_T = \{0, 1\} \)
\( V_N = \{S\} \)
\( R = \{ S \rightarrow 1S \mid 0S \mid \epsilon; S \rightarrow 1S \mid \epsilon \} \)
f) \( L_6 = \{ w \in \{0, 1\}^* \mid w \) ne contient ni 1 consécutifs ni 0 consécutifs \}
Soit \( G_6 = (V_T, V_N, S, R) \), où :
\( V_T = \{0, 1\} \)
\( V_N = \{S, A, B\} \)
\( R = \{ S \rightarrow 1A \mid 0B \mid \epsilon; A \rightarrow 0B \mid \epsilon; B \rightarrow 1A \mid \epsilon \} \)
Exercice 4
Soit le langage \( L \) défini sur \( V = \{a, b, c\} \) comme suit : \( L = \{ a^{2n} bc^{2m+1} \mid n, m \geq 0 \} \)
a) Trouver une grammaire de type 2 qui engendre \( L \)
Soit \( G = (V_T, V_N, S, R) \), où :
\( V_T = \{a, b, c\} \)
\( V_N = \{S, A, B\} \)
\( R = \{ S \rightarrow AbB; A \rightarrow aaA \mid \epsilon; B \rightarrow ccB \mid c \} \)
b) Montrer que \( L \) est de type 3
Soit une grammaire de type 3 \( G_1 = (V_T, V_N, S, R) \), où :
\( V_T = \{a, b, c\} \)
\( V_N = \{S, A, C, D\} \)
\( R = \{ S \rightarrow aA \mid bC; A \rightarrow aS; C \rightarrow cD \mid c; D \rightarrow cC \mid \epsilon \} \)
Exercice 5
Soit le langage \( L \) défini comme l'ensemble de tous les mots de \( \{0, 1\}^* \) qui contiennent un nombre pair de « 1 ».
a) Trouver une grammaire de type 2 qui engendre \( L \)
\( G = (\{0, 1\}, \{S\}, S, R) \), où \( R = \{ S \rightarrow 0S \mid 1S1S \mid \epsilon \} \)
b) Montrer que \( L \) est de type 3
\( L \) peut être généré par une grammaire de type 3 \( G' = (\{0, 1\}, \{S, A\}, S, R') \), où \( R' = \{ S \rightarrow 0S \mid 1A; A \rightarrow 0A \mid 1S \} \)
Exercice 6
Soit la grammaire \( G = (V_T, V_N, S, R) \), où :
\( V_T = \{a, b, c\} \)
\( V_N = \{S, B, H, D\} \)
\( R = \{ S \rightarrow cBc; B \rightarrow baH \mid bD; D \rightarrow bDa \mid ba; H \rightarrow baB \} \)
Quel est le langage engendré par \( G \) ?
\( L(G) = \{ w \in \{a, b, c\}^* \mid w = c(ba)^n b^{m+1} a^m c, n \geq 0 \text{ et } m \geq 1 \} \)
Exercice 7
Soit la grammaire \( G = (V_T, V_N, S, R) \), où :
\( V_T = \{a, b\} \)
\( V_N = \{S\} \)
\( R = \{ S \rightarrow aSa \mid bSb \mid a \mid b \} \)
a) Quel est le type de \( G \) ?
\( G \) est de type 2.
b) Déterminer le langage \( L \) engendré par \( G \).
\( L = \{ w \in \{a, b\}^* \mid w \) est un palindrome de taille impaire \}.
c) Quel est son type ?
\( L \) est de type 2 car il nécessite des puissances liées entre les symboles des mots.
Exercice 8
Soit la grammaire \( G = (V_T, V_N, S, R) \), où :
\( V_T = \{a, b\} \)
\( V_N = \{S, A, B\} \)
\( R = \{ S \rightarrow AB \mid \epsilon; A \rightarrow aAb \mid \epsilon; B \rightarrow bBb \mid b \} \)
a) Quel est le type de \( G \) ?
\( G \) est de type 1 car toutes les règles sont de type 1.
b) Déterminer le langage \( L \) engendré par \( G \).
\( L(G) = \{ w \in \{a, b\}^* \mid w = a^n b^m \text{ avec } n \geq 0 \text{ et } 0 \leq m \leq 2n \} \)
c) Quel est son type ?
\( L \) est de type 2 car il peut être généré par une grammaire équivalente de type 2 :
\( G' = (\{a, b\}, \{S, B\}, S, R') \), où \( R' = \{ S \rightarrow aSbB \mid \epsilon; B \rightarrow \epsilon \mid b \} \)
Exercice 9
1) Soit le langage \( L = \{ a^n b^m \mid n \neq m, n \text{ et } m \in \mathbb{N} \} \)
a) Donner une grammaire \( G \) engendrant \( L \).
\( G = (V_T, V_N, S, R) \), où :
\( V_T = \{a, b\} \)
\( V_N = \{S, A, B, D\} \)
\( R = \{ S \rightarrow AB \mid BD; A \rightarrow aA \mid \epsilon; B \rightarrow bB \mid \epsilon; D \rightarrow bD \mid \epsilon \} \)
b) Donner le type de \( L \).
\( L \) est de type 2.
2) Donner une grammaire de type 2 qui génère \( L = \{ a^n b^n c^m \mid n, m \geq 0 \} \cup \{ a^n b^m c^m \mid n, m \geq 0 \} \cup \{ a^n b^m c^n \mid n, m \geq 0 \} \).
\( G = (V_T, V_N, S, R) \), où :
\( V_T = \{a, b, c\} \)
\( V_N = \{S, A, B, C, D, E\} \)
\( R = \{ S \rightarrow AB \mid C \mid E; A \rightarrow aAb \mid \epsilon; B \rightarrow bcB \mid \epsilon; C \rightarrow aCc \mid D; D \rightarrow bD \mid \epsilon; E \rightarrow aE \mid F; F \rightarrow bFc \mid \epsilon \} \)
Exercice 10
Soit la grammaire \( G = (V_T, V_N, S, R) \), où :
\( V_T = \{a, b\} \)
\( V_N = \{S\} \)
\( R = \{ S \rightarrow aSa \mid bSb \mid \epsilon \} \)
a) Montrer que \( aabbaa \in L(G) \).
Par dérivation : \( S \rightarrow aSa \rightarrow aaSaa \rightarrow aabbaa \).
b) Quel est le langage \( L \) engendré par \( G \) ?
\( L = \{ w \in \{a, b\}^* \mid w = w_1 w_2 w_1 \} \), où \( w_1 \) et \( w_2 \) sont des mots de \( \{a, b\}^* \).
Exercice 11
Soit la grammaire \( G = (\{a, b, d\}, \{S, B, C\}, S, R) \), où :
\( R = \{ S \rightarrow aSBC \mid bB \mid b^2 S \mid aBC \mid bC \mid bd; CB \rightarrow BC; BC \rightarrow dC; dC \rightarrow d^2; aB \rightarrow ab \} \)
Quel est le langage \( L \) engendré par \( G \) ?
\( L = \{ a^n b^n d^n \mid n \geq 1 \} \).
Ce langage est de type 1.
Exercice 12
Soit la grammaire \( G = (V_T, V_N, S, R) \), où :
\( V_T = \{a, b\} \)
\( V_N = \{S\} \)
\( R = \{ S \rightarrow aSa \mid aS \mid bS \mid a \mid b \} \)
a) Quel est le type de \( G \) ?
\( G \) est de type 2.
b) Quel est le langage \( L \) engendré par \( G \) ?
\( L(G) = \{a, b\}^+ \).
c) Quel est son type ?
\( L \) est de type 3 car il peut être généré par une grammaire de type 3 équivalente :
\( G' = (\{a, b\}, \{S\}, S, R') \), où \( R' = \{ S \rightarrow aS \mid bS \mid a \mid b \} \).
FAQ
Qu'est-ce qu'une grammaire de type 2 ?
Une grammaire de type 2 est une grammaire contextuelle libre, où les règles de production sont de la forme \( A \rightarrow \alpha \) avec \( A \in V_N \) et \( \alpha \in (V_T \cup V_N)^* \). Elle permet de générer des langages contextuels libres.
Comment déterminer si un langage est de type 3 ?
Un langage est de type 3 s'il peut être engendré par une grammaire linéaire, c'est-à-dire une grammaire où toutes les règles sont de la forme \( A \rightarrow xB \) ou \( A \rightarrow x \), avec \( x \in V_T^* \) et \( A, B \in V_N \).
Quelle est la différence entre une grammaire de type 1 et une grammaire de type 2 ?
Une grammaire de type 1 (monotone) a des règles de la forme \( \alpha A \rightarrow \alpha \beta \) avec \( A \in V_N \) et \( \alpha, \beta \in (V_T \cup V_N)^* \), tandis qu'une grammaire de type 2 (libre de contexte) a des règles de la forme \( A \rightarrow \alpha \) avec \( A \in V_N \) et \( \alpha \in (V_T \cup V_N)^* \).