Colle 2 : Grammaires et graphes
Voici la liste des compétences et connaissances à avoir pour votre deuxième colle.
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.