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

Autres pages du cours

  • sur moodle (supports, informations, modalités d’examens, etc.)
  • sur unige (informations administratives)

Notes de cours

Les notes de cours sont déposées ici (et sur Moodle) au fur et à mesure du semestre.

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.

Pour aller plus loin

Une partie du cours s’inspire de “Introduction to the Theory of Computation (Michael Sipser)”. D’autres parties sont composées à partir de ressources variées, dont certains articles Wikipédia. Vous pouvez aussi consulter les notes de cours des années précédentes sur cette page.