Langages réguliers et expressions régulières

Grammaire

On rappelle qu’une grammaire G1 = (T, N, S, R) est régulière à droite si les règles de R sont de la forme : A → aB ou A → a avec A, B ∈ N et a ∈ T.

On rappelle qu’une grammaire G2 = (T, N, S, R) est régulière à gauche si les règles de R sont de la forme : A → Ba ou A → a avec A, B ∈ N et a ∈ T.

Un langage est régulier ou rationnel si et seulement s’il existe une grammaire régulière générant ce langage.

L’intérêt de distinguer grammaires régulières à droite ou à gauche apparaît lors de l’analyse : si on lit les symboles du mot à analyser de la gauche vers la droite, alors

  • une grammaire régulière à droite sera utilisée pour une analyse descendante, de l’axiome vers le mot
  • une grammaire régulière à gauche sera utilisée pour une analyse ascendante, du mot vers l’axiome.

Par exemple, pour analyser le mot aaabb avec la grammaire G1, on construira la dérivation S1 ⇒ aS1 ⇒ aaS1 ⇒ aaaU1 ⇒ aaabU1 ⇒ aaabb; tandis que pour analyser ce mot avec la grammaire G2, on construira la dérivation aaabb ⇐ U2aabb ⇐ U2abb ⇐ U2bb ⇐ S2b ⇐ S2.

Langage et expression

Une expression E est une expression régulière sur un alphabet A si et seulement si :

  • E = ∅ ou
  • E = ε ou
  • E = a avec a ∈ A ou
  • E = E1 | E2 et E1 et E2 sont deux expressions régulières sur A ou
  • E = E1.E2 et E1 et E2 sont deux expressions régulières sur A ou
  • E = E1 et E1 est une expression régulière sur A

Les opérateurs ∗, . et | ont une priorité décroissante. Si nécessaire, on peut ajouter des parenthèses.

Le langage L(E) décrit par une expression régulière E définie sur un alphabet A est défini par

  • L(E) = ∅ si E = ∅,
  • L(E) = {ε} si E = ε,
  • L(E) = {a} si E = a,
  • L(E) = L(E1) ∪ L(E2) si E = E1 | E2,
  • L(E) = L(E1).L(E2) si E = E1.E2,
  • L(E) = L(E1) si E = E1 et E1 est une expression régulière sur A.

L’équivalence entre expressions régulières et langages réguliers est établie par les deux implications suivantes :

  • Toute expression régulière décrit un langage régulier.
  • Tout langage régulier peut être décrit par une expression régulière.

Processus de création d’automate à partir d’une expression régulière

langage21

Publicités