Colle 1 : Langages, automates et grammaires

Voici la liste des compétences et connaissances à avoir pour votre première colle. La colle est constituée d'un ou plusieurs exercices.

Langages :

• Définitions et opérations sur les mots et langages
• Montrer l'égalité de deux langages (double inclusion...)
• Montrer une propriété par récurrence sur des mots
• Connaître la définition de langage régulier
• Montrer qu'un langage est régulier (éventuellement en passant par une expression régulière)
• Connaître la syntaxe des expressions régulières
• Montrer une propriété sur les langages réguliers (ou expressions régulières) par induction structurelle
• Écrire un programme OCaml pour manipuler une expression régulière

Automates :

• Définitions
• Écrire un programme OCaml pour manipuler un automate
• Montrer qu'un langage est reconnaissable
• Trouver le langage reconnu par un automate
• Compléter un automate
• Algorithme de déterminisation et automate des parties
• Stabilité des langages reconnaissables par complémentaire, intersection, union, différence. Automate produit.
• États accessibles et co-accessibles. Automate émondé. Tout automate est équivalent à un automate émondé.
• Lemme de l'étoile, avec démonstration et application pour montrer qu'un langage n'est pas reconnaissable.

Théorème de Kleene :

• Langage local, expression régulière linéaire.
• Algorithme de Berry-Sethi pour construire un automate (de Glushkov) à partir d'une expression régulière.
• ε-transitions. Tout automate avec des ε-transitions est équivalent à un automate sans ε-transition.
• Automate de Thompson (construit récursivement) à partir d'une expression régulière.
• Méthode d'élimination des états pour obtenir une expression régulière à partir d'un automate.
• Théorème de Kleene et conséquences.

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.