Cette page contient les ressources pédagogiques du cours de Langages Formels des années précédentes. Pour l’année actuelle, ça se passe sur cette page.

Automne 2024

Enseignant : Arnaud Casteigts
Assistant : Alexandre-Quentin Berger et Matteo De Francesco
Monitrices : Léa Heiniger et Aylin Tekkoyun

Automne 2023

Enseignant : Arnaud Casteigts
Assistant : Alexandre-Quentin Berger
Monitrices : Léonie Dezempte et Léa Heiniger

Réponses à quelques questions posées en amphi:

  • Le lemme de l’étoile donne une condition nécessaire pour être un langage régulier (vous savez cela). Est-ce aussi une condition suffisante ?

→ Non, il existe des langages non-réguliers qui la satisfont malgré tout, par exemple le langage: \(L = \{ a b^n c^n : n \geq 0 \} \cup \{ a^k w : k \neq 1 \text{ et } w \text{ commence par $a$} \}.\)

  • La notion d’arbre de syntaxe abstraite (abstract syntax tree, AST) est-elle la même que les arbres de dérivations ?

→ Non, pas tout à fait, mais c’est très lié. Il s’agit d’une représentation simplifiée que l’on peut construire à partir des arbres de dérivations et qui facilitent leur utilisation ultérieure.