Colle 2 : Grammaires et graphes

Voici la liste des compétences et connaissances à avoir pour votre deuxième colle ainsi que le DS 2.

Grammaires :

• Grammaire non-contextuelle (algébrique, hors-contexte).
• Dérivation.
• Langage engendré. Savoir démontrer par récurrence (sur la longueur du mot ou de la dérivation) que le langage engendré par G est bien ce qu'on souhaite.
• Les langages réguliers sont algébriques.
• Arbre de dérivation.
• Grammaire ambigüe. Dérivation gauche. Savoir montrer qu'une grammaire est ambigüe.
• Analyse syntaxique : exemple.

Révisions sur les graphes :

• Définitions : degré, voisins...
• Chemin, cycle, connexité.
• Connexe à $n$ sommets $\Rightarrow$ au moins $n - 1$ arêtes.
• Acyclique à $n$ sommets $\Rightarrow$ au plus $n - 1$ arêtes.
• Composantes connexes, composantes fortement connexes.
• Un graphe est un arbre ssi il est connexe acyclique ssi connexe et $n - 1$ arêtes ssi acyclique et $n - 1$ arêtes.
• Représentations par matrice et liste d'adjacence.
• Parcours en largeur et profondeur. Application à la connexité et à la recherche de cycle.

Arbres couvrants :

• Définition.
• Algorithme de Kruskal. Correction.
• Union-Find avec compression de chemin et union par rang.