Julien Marcil - julien.marcil@ift.ulaval.ca
Définition: Un langage est dit régulier s’il existe un automate fini déterministe qui le reconnaît.
Une façon de montrer qu’un langage est régulier est de construire un automate qui reconnaît ce langage.
Soit le langage $L=\{w \mid w$ contient le même nombre de $0$ et de $1\}$. Est-ce que $L$ est régulier?
Si $L$ est un langage régulier, alors il existe un entier $p \ge 1$ (appelé longueur de pompage) tel que pour tout mot $w \in L$ avec $\lvert w \rvert \ge p$, il existe des mots $x,y,z$ tels que $w = xyz$ et
Pour prouver qu’un langage est non régulier, on fait une preuve par contradiction.
Prouver que le langage $L = \{0^n1^n \mid n \in \mathbb N\}$ n'est pas régulier.
Prouver que le langage $L=\{w \mid w \text{ contient le même nombre de 0 et de 1} \}$ n'est pas régulier.
Prouver que le langage $L = \{0^i1^j \mid i > j \}$ n'est pas régulier.
Prouver que le langage $L = \{0^i1^j \mid i \ne j \}$ n'est pas régulier.
Prouver que le langage $L = \{1^{n^2} \mid n \in \mathbb N \}$ n'est pas régulier.
$$L = \{ 1, 1111, 11111111111, ... \}$$
Est-ce que le langage $L = \{w \mid w $ contient le même nombre de sous-chaînes $01$ et $10 \}$ est régulier?
Soit $\Sigma = \{ 0, 1 \}$ et $$ \begin{align} A = & \{ 0^ku0^k \mid k \ge 1, u \in \Sigma^* \} \\ B = & \{ 0^k1u0^k \mid k \ge 1, u \in \Sigma^* \} \end{align} $$
Dans cette section, nous verrons un nouvel outil servant à la génération de langages: les grammaires.
Changement de point de vue: au lieu de considérer des machines qui reconnaissent un langage donné, on construit un ensemble de règles qui servent à construire les mots d’un langage.
Une grammaire consiste en un ensemble fini de règles de réécriture (ou règles de productions ou règles de substitution).
$$ \begin{align} S \rightarrow & 0S1 \\ S \rightarrow & B \\ B \rightarrow & \lambda \end{align} $$
Une grammaire génère une séquence par dérivation.
$$ \begin{align} S ⇒ & 0S1 \\ ⇒ & 00S11 \\ ⇒ & 000S111 \\ ⇒ & 000B111 \\ ⇒ & 000\lambda111 \\ ⇒ & 000111 \end{align} $$
Définition: Une grammaire consiste en un quadruplet de la forme $(V, \Sigma, S, R)$ où
Ces règles sont formées d’un terme de gauche, d’une flèche ($\rightarrow$) et d’un terme de droite.
Les termes gauche et droit peuvent être n’importe quelle combinaison de symboles de $V$ ou de $\Sigma$, pourvu qu’il y ait au moins un symbole de $V$ à gauche. Le côté droit peut être vide, ce qui est indiqué par un $\lambda$.
Voici une grammaire $(V,\Sigma,S,R)$ où
$
\begin{align}
V & = \{S, A, B, C\} \\
\Sigma & = \{a, b, c\} \\
S &\text{est le symbole de départ }
\end{align}
$
$
\begin{alignat}{2}
R = \{ \ & S & \rightarrow & ASC \\
& S & \rightarrow & B \\
& B & \rightarrow & bB \\
& B & \rightarrow & \lambda \\
& A & \rightarrow & a \\
& C & \rightarrow & c \
\}
\end{alignat}
$
Cette convention permet de simplifier la description d’une grammaire en donnant seulement la description de $R$.
$$ \begin{align} S & \rightarrow ASC & S & \rightarrow B \\ B & \rightarrow bB & B & \rightarrow \lambda \\ A & \rightarrow a & C & \rightarrow c \ \end{align} $$
Il est possible de noté les règles de réécriture plus simplement
$$ \begin{align} S & \rightarrow ASC \mid B \\ B & \rightarrow bB \mid \lambda \\ A & \rightarrow a \\ C & \rightarrow c \ \end{align} $$
On nomme production l'application d'une régle de de réécriture à une chaîne de symboles terminaux et non terminaux.
Soit $u, v, w \in (V \cup \Sigma)^*$, et la régle de de réécriture $A \rightarrow w$. On dit que $uAv$ produit $uwv$, noté
$$uAv \Rightarrow uwv$$
On nomme dérivation l'application d'une ou plusieurs régles de de réécriture à une chaîne de symboles terminaux et non terminaux.
Soit $u, v \in (V \cup \Sigma)^*$ on dit $u$ dérive $v$, noté $$ u \overset{*}{\Rightarrow} v $$
si $u = v$ ou s'il existe $u_1,u_2,...,u_k$ pour $k \ge 0$ et
$$u⇒u1 ⇒u2 ⇒...⇒uk ⇒v$$
Soit la gramaire $G = (V, \Sigma, S, R)$.
$$L(G) = \{ w \in Σ^* \mid S \overset{*}{\Rightarrow} w \}$$
On dit que $L(G)$ est le langage généré par $G$.
$$ \begin{align} S & \rightarrow ASC & S & \rightarrow B \\ B & \rightarrow bB & B & \rightarrow \lambda \\ A & \rightarrow a & C & \rightarrow c \ \end{align} $$
$$ \begin{align} S & \rightarrow abNSc & bNa & \rightarrow abN \\ S & \rightarrow \lambda & bNb & \rightarrow bbN \\ & & bNc & \rightarrow bc \ \end{align} $$
Soit $\Sigma=\{0,1\}$. Trouver une grammaire pour les langages suivants: