TDs d'automates et applications
TD numéro 3

Table des matières

• Langage (a b + b a)⁺
• Langage des identificateurs
• Langage avec « 0011 »
• Langage sans « 101 »

Soit la grammaire G suivante. Quel est son type (0, 1, 2 ou 3) ? Quelle est l'expression régulière du langage engendré ?

G = < {a}, {S, A, B}, S, R >
avec R: 
  S --> a B | b A
  A --> a | a S
  B --> b | b S

Cette grammaire est régulière, c'est-à-dire de type 3. En effet toutes les règles sont linéaires à droite. Pour trouver l'expression régulière du langage engendré, il faut résoudre le système suivant :

  S = a B + b A
  A = a + a S
  B = b + b S

Ce qui nous donne :

  S = a (b + b S) + b (a + a S)
    = (a b + b a) S + (a b + b a)

D'après le théoreme de Arden vu en cours, on obtient :

  S = (a b + b a)* . (a b + b a)
    = (a b + b a)+

Soit la grammaire G suivante. Quel est son type (0, 1, 2 ou 3) ? Quelle est l'expression régulière du langage engendré ?

G = < {l,c}, {S, A}, S, R >
avec R: 
  S --> l A
  A --> l A | c A | epsilon

Cette grammaire est régulière, c'est-à-dire de type 3. En effet toutes les règles sont linéaires à droite. Pour trouver l'expression régulière du langage engendré, il faut résoudre le système suivant :

  S = l A
  A = l A + c A + epsilon
    = (l + c) A + epsilon

Le théorème de Arden nous permet de résoudre l'équation de A et de trouver :

  A = (l + c)* . epsilon
    = (l + c)*

Par conséquent :

  S = l . (l + c)*

Trouver une grammaire G engendrant le langage construit sur le vocabulaire V_T = {0,1} et tel que toute chaîne « 00 » est toujours suivie de la chaîne « 11 ». Quel est son type (0, 1, 2 ou 3) ? Quelle est l'expression régulière du langage ?

G = < {0,1}, {S}, S, R >
avec R: 
  S --> 1 S | 01 S | 0011 S | 0 | epsilon

Cette grammaire est régulière, c'est-à-dire de type 3. En effet toutes les règles sont linéaires à droite. Pour trouver l'expression régulière du langage engendré, il faut résoudre le système suivant :

  S = 1 S + 01 S + 0011 S + 0 + epsilon
    = (1 + 01 + 0011) S + (0 + epsilon)

Le théorème de Arden nous permet de résoudre cette équation et de trouver :

  S = (1 + 01 + 0011)* . (0 + epsilon)

Trouver une grammaire G engendrant le langage construit sur le vocabulaire V_T = {0,1} et ne contenant jamais la chaîne « 101 ». Quel est son type (0, 1, 2 ou 3) ? Quelle est l'expression régulière du langage ?

G = < {0,1}, {S,A}, S, R >
avec R: 
  S --> 0 S | 1 A | epsilon
  A --> 1 A | 00 S | 0 | epsilon

Cette grammaire est régulière, c'est-à-dire de type 3. En effet toutes les règles sont linéaires à droite. Pour trouver l'expression régulière du langage engendré, il faut résoudre le système suivant :

  S = 0 S + 1 A + epsilon
  A = 1 A + 00 S + 0 + epsilon

Le théorème de Arden ne nous permet pas de résoudre ces équations ! Certes, chaque équation est bien de la forme « X = alpha X + beta ». Mais dans les deux cas, beta n'est pas un sous-ensemble de V_T^*. La solution consiste à résoudre d'abors la seconde équation en prenant V_T = {0,1,S} et V_N = {1}. On trouve :

  A = 1* . (00 S + 0 + epsilon)

A présent on substiue dans l'équation de S et on trouve :

  S = 0 S + 1 . 1* . (00 S + 0 + epsilon) + epsilon
    = (0 + 1+00) S + (1+0 + 1+ + epsilon)

Pour finir, on résoud cette équation normalement :

  S = (0 + 1+00)* . (1+0 + 1*)