Agrégation informatique externe 2023, épreuve 2Sujet et rapport du jury

AGREGATION
CONCOURS EXTERNE

INFORMATION AUX CANDIDATS

Ces codes doivent être reportés sur chacune des copies que vous remettrez.

Test d'égalité de langages rationnels

Partie I. Préliminaires algorithmiques

1 Tableaux redimensionnables

• -initialisation : crée un tableau redimensionnable vide ne contenant aucune donnée (en Python, c'est l'instruction t = [] );
• -longueur : renvoie le nombre d'éléments stockés dans le tableau redimensionnable (en Python, c'est l'instruction len(t));
• -accès : permet d'accéder en lecture et en écriture à l'élément en i-ème position dans un tableau redimensionnable ; les indices commencent à 0, donc il faut que i soit compris entre 0 et la longueur moins 1 (en Python, c'est t [i] ).
• -ajout à la fin : ajoute une donnée après la dernière donnée existante du tableau redimensionnable (en Python, c'est l'instruction t.append(x));

• -allouer un tableau de taille n en temps O(n);
• -accéder au i-ème élément d'un tableau en temps O(1);
• -affecter une valeur au i-ème élément d'un tableau en temps O(1).

Figure 1 - Représentation de la liste abstraite [8,4,-2,7,11] au moyen d'un tableau redimensionnable de capacité 8.

• -initialisation : crée un enregistrement avec capacite=1, longueur=0 et alloue une case pour tableau;
• -longueur : renvoie longueur ;
• -accès : renvoie tableau[i] ;
• -ajout à la fin : il y a deux cas selon que l'on ait la place pour un nouvel élément ou non
  • -si longueur < capacite, on place le nouvel élément dans la case d'indice longueur du champs tableau et on incrémente longueur;
  • -si longueur == capacite, on alloue un nouveau tableau de capacite doublée, on recopie tous les éléments de l'ancien tableau dedans, puis on place le nouvel élément dans la case d'indice longueur du champs tableau et on incrémente longueur.

2 Tri lexicographique

• -Créer un tableau redimensionnable T contenant c tableaux redimensionnables initialement vides.
• -Pour chaque élément (liste de longueur k ) ℓ de L dans l'ordre, ajouter ℓ en fin du tableau redimensionnable T[ℓ[j]].
• -Renvoyer la concaténation des tableaux redimensionnables T[0], T[1], …, T[c − 1].

Partie II. Des expressions rationnelles aux automates

3 Représenter des expressions rationnelles non vides

• -l'ensemble d'assertions {ε, a|a ∈ Σ},
• -l'ensemble de règles d'inférence {somme : (E_1, E_2) ↦ (E_1) + (E_2), étoile : E ↦ (E)^∗, produit : (E_1, E_2) ↦ (E_1) ⋅ (E_2)}.

expression(['+', [ '*', [ '.', [ 'a'] , [ 'b'] ] ], ['+', [ '.', ['a'], ['a']], ['']]])
s’évalue en ’(((a).(b))*)+(((a).(a))+(_))’, où le caractère ’_’ représente le mot vide.

4 Automate de Glushkov

4.1 Rappels et propriétés

linearisation([’+’, [’*’, [’.’, [’a’] , [’b’] ] ], [’+’, [’.’, [’a’], [’a’]], [’’]])
s'évalue en ['+', ['*', ['.', ['a1'], ['b2']]], ['+', ['.', ['a3'], ['a4']], ['']]].

• - First(E) est l'ensemble des lettres de Σ_ℓ qui apparaissent au début d'un mot de L(E_ℓ) :
  First(E) = {x ∈ Σ_ℓ|∃u ∈ Σ_ℓ^∗, xu ∈ L(E_ℓ)},
• -Last (E) est l'ensemble des lettres de Σ_ℓ qui apparaissent à la fin d'un mot de L(E_ℓ) :
  Last(E) = {x ∈ Σ_ℓ|∃u ∈ Σ_ℓ^∗, ux ∈ L(E_ℓ)},
• - Null(E) = vrai si L(E_ℓ) contient le mot vide, et faux sinon;
• - Follow(E) est l'ensemble des facteurs de longueur 2 des mots de L(E_ℓ) :
  Follow(E) = {xy ∈ Σ_ℓ^2|∃u, v ∈ Σ_ℓ^∗, uxyv ∈ L(E_ℓ)}.

• -pour toute lettre x ∈ First(E), on a la transition δ_ℓ(i, x) = {x} de l'état i par la lettre x,
• -pour toute lettre x ∈ Σ_ℓ et toute lettre y ∈ Σ_ℓ telles que xy ∈ Follow(E), on a la transition δ_ℓ(x, y) = {y} de l'état x par la lettre y,
• -l'ensemble des états finaux F = Last(E) ∪ {i} si Null(E) est vrai, et F = Last(E) sinon.

4.2 Construction de l'automate

class Set(builtins.object)
    représentation d'un ensemble fini
    Methods defined here:
    disjoint_extend(self, other)
        modifie l'objet courant en l'étendant avec le contenu de
        l'objet passé en paramètre et renvoie l'objet courant ainsi modifié,
        les deux objets doivent représenter des ensembles disjoints,
        le résultat représente l'union des deux ensembles;
        cette méthode s’exécute en temps linéaire en la taille de
        l'ensemble fourni en argument.
    empty()
        renvoie un ensemble vide;
        cette méthode s’exécute en temps constant.
    extend(self, other)
        modifie l'objet courant en l'étendant avec le contenu de
        l'objet passé en paramètre et renvoie l'objet courant ainsi modifié,
        le résultat représente l'union des deux ensembles (sans doublons);
        cette méthode s’exécute en temps proportionnel au produit
        de la taille de l'ensemble sur lequel la méthode est
        invoquée et de la taille de l'ensemble fourni en argument.
    product(self, other)
        renvoie le produit cartésien de deux langages,
        le résultat est un ensemble de couples;
        cette méthode s’exécute en temps proportionnel au produit
        de la taille de l'ensemble sur lequel la méthode est
        invoquée et de la taille de l'ensemble fourni en argument.
    singleton(e)
        renvoie un singleton contenant l'élément fourni en argument;
        cette méthode s'exécute en temps constant.

def glushkov(exp):
"""renvoie first, last, null et follow de l'expression exp
exp doit être locale et non vide
first, last et follow sont des instances de Set, null est un booléen"""
assert(len(exp) > 0 and len(exp) <= 3)
if len(exp) == 1:
    if exp[0] == ’’:
        first, last, null, follow = Set.empty(), Set.empty(), True, Set.empty()
    else:
        first, last = Set.singleton(exp[0]), Set.singleton(exp[0])
        null, follow = False, Set.empty()
elif len(exp) == 3:
    assert(exp[0] in [’+’, ’.’])
    first1, last1, null1, follow1 = glushkov(exp[1])
    first2, last2, null2, follow2 = glushkov(exp[2])
    if exp[0] == '+':
        first = first1.disjoint_extend(first2)
        last = last1.disjoint_extend(last2)
        null = null1 or null2
        follow = follow1.disjoint_extend(follow2)
    else:
        first = first1 if not null1 else first1.disjoint_extend(first2)
        last = last2 if not null2 else last2.disjoint_extend(last1)
        null = null1 and null2
        follow = follow1.disjoint_extend(follow2).disjoint_extend(last1.product(first2))
else:
    assert(exp[0] == '*')
    first1, last1, null1, follow1 = glushkov(exp[1])
    first, last, null = first1, last1, True
    follow = follow1.extend(last1.product(first1))
return first, last, null, follow

[’+’, [’*', [’.’, [’a1’] , [’b2’] ] ], [’.’, [’a3’], [’a4’]]].

4.3 Amélioration de la complexité

Partie III. Test d'égalité de langages reconnus par automates

• - Σ est un alphabet fini non vide contenant les lettres;
• - Q est un ensemble fini non vide contenant les états;
• - δ : Q × Σ → Q est l'application des transitions ;
• - i_0 ∈ Q est l'état initial;
• - F ⊆ Q est l'ensemble des états terminaux.

5 Partitions des états

Question 34. On considère l'automate ci-dessous et la partition P = {{0, 1}, {2, 3}} de son ensemble d'états. Calculer le Σ-raffinement de P.

• -delta est une liste contenant n listes de longueur m, appelé la table des transitions ; pour tous états p, q ∈ {0, …, n − 1} et toute lettre a ∈ {0, …, m − 1} on a delta[p] [a]=q si et seulement si p → ^a q (on rappelle que les automates de cette partie sont déterministes et complets, ce qui permet un tel encodage);
• -F est une liste de n booléens avec, pour tout état p ∈ {0, …, n − 1}, F[p] = True si et seulement si p est terminal.

s[p] = [part[p], part[ delta[p][0] ], ..., part[ delta[p][m-1] ], p].

6 Partition de Nerode

def moore(A):
    """A est un automate déterministe et complet,
    qui respecte l'encodage du sujet. la fonction renvoie
    la partition de Nerode de A."""
    ancienne_part = None
    part = calcule_partition0(A)
    while nombre_parts(ancienne_part) != nombre_parts(part):
        ancienne_part = part
        part = raffine(A, part)
    return part

7 Test d'égalité utilisant la partition de Nerode