IFT-2002

Informatique Théorique

H14 - cours 4


Julien Marcil - julien.marcil@ift.ulaval.ca

Cours précédents

Langage régulier

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.

Aujourd'hui

  • Langage non régulier
  • Grammaire

Langage non régulier

Observation

Soit le langage $L=\{w \mid w$ contient le même nombre de $0$ et de $1\}$. Est-ce que $L$ est régulier?

Lemme de pompage

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

  1. $\lvert xy \rvert \le p$
  2. $\lvert y \rvert > 0$
  3. pour tout entier $i \ge 0$ on a $xy^iz \in L$

Preuve qu’un langage $L$ est non régulier

Pour prouver qu’un langage est non régulier, on fait une preuve par contradiction.

  • On suppose que $L$ est régulier.
  • Donc il existe $p$ la longueur de pompage de $L$.
  • On choisi un mot $w \in L$, avec $\lvert w \rvert \ge p$ (qu'il ne sera pas possible de pomper).
  • On montre qu'en pompant $w$, on génère des mots qui ne sont pas dans $L$.

Exemple

Prouver que le langage $L = \{0^n1^n \mid n \in \mathbb N\}$ n'est pas régulier.

Exemple

Prouver que le langage $L=\{w \mid w \text{ contient le même nombre de 0 et de 1} \}$ n'est pas régulier.

Exemple

Prouver que le langage $L = \{0^i1^j \mid i > j \}$ n'est pas régulier.

Exemple

Prouver que le langage $L = \{0^i1^j \mid i \ne j \}$ n'est pas régulier.

Exemple

Prouver que le langage $L = \{1^{n^2} \mid n \in \mathbb N \}$ n'est pas régulier.

$$L = \{ 1, 1111, 11111111111, ... \}$$

Exemple

Est-ce que le langage $L = \{w \mid w $ contient le même nombre de sous-chaînes $01$ et $10 \}$ est régulier?

Exemple

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} $$

  • Montrer que $A$ est régulier
  • Montrer que $B$ est non régulier

Grammaire

Introduction

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.

Grammaire

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} $$

Dérivation

Une grammaire génère une séquence par dérivation.

$$ \begin{align} S ⇒ & 0S1 \\ ⇒ & 00S11 \\ ⇒ & 000S111 \\ ⇒ & 000B111 \\ ⇒ & 000\lambda111 \\ ⇒ & 000111 \end{align} $$

Grammaire

Définition: Une grammaire consiste en un quadruplet de la forme $(V, \Sigma, S, R)$ où

  • $V$ est ensemble fini de variables (symboles non terminaux).
  • $\Sigma$ est l’alphabet (symboles terminaux).
  • $S \in V$ est le symbole de départ.
  • $R$ est un ensemble fini de règles de réécriture.

Règles de réécriture

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$.

Exemple

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} $

Conventions

  • Les majuscules sont des symboles non terminaux.
  • Les minuscules sont des symboles terminaux.
  • $S$ est le symbole initial.

Cette convention permet de simplifier la description d’une grammaire en donnant seulement la description de $R$.

Notation

$$ \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} $$

Production

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$$

Dérivation

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$$

Langage généré par $G$

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$.

Exemple

$$ \begin{align} S & \rightarrow ASC & S & \rightarrow B \\ B & \rightarrow bB & B & \rightarrow \lambda \\ A & \rightarrow a & C & \rightarrow c \ \end{align} $$

Exemple

$$ \begin{align} S & \rightarrow abNSc & bNa & \rightarrow abN \\ S & \rightarrow \lambda & bNb & \rightarrow bbN \\ & & bNc & \rightarrow bc \ \end{align} $$

Exemples

Soit $\Sigma=\{0,1\}$. Trouver une grammaire pour les langages suivants:

  • $\{ w \mid w$ contient trois $1\}$
  • $\{ w \mid w$ commence et finit par le même symbole $\}$
  • $\{ w \mid \lvert w \rvert \ mod \ 2 = 1\}$
  • $\{ w \mid \lvert w \rvert \ mod \ 2 = 1$ et $0$ au centre$\}$
  • $\{ w \mid w = w^R \}$