Théorie des langages

Responsable : Alexis Nasr

Informations

07/12/2017 heure de passage pour l'évaluation des TP

28/11/2017 les notes du partiel PDF

Istructions pour l'affichage des automates à l'aide de la commande draw:

Télécharger xdot et le placer dans le même répertoire que votre interpréteur
Lui donner les droits d'execution avec la commande "chmod +x xdot"
Télécharger le fichier draw.c et copier la fonction draw_automaton dans Automaton.c
Recompiler et executer la commande draw sur un automate

Théorie des langages
Organisation et contenu du cours

Modalités de contrôle

Evaluation du projet

Machines de Turing

Examens des années précédentes

Bibliographie

Organisation et contenu du cours

Semaine	Date	mercredi 10h - 12h	groupe 1 : mercredi 13h30 - 15h30	groupe 1 : mercredi 15h30 - 17h30
			groupe 2 : mercredi 13h30 - 15h30	groupe 2 : mardi 10h00 - 12h00
1	11/09/17	CM 1 : Introduction Langages réguliers - Expressions régulières	TD 1 : Expressions régulières	TP 1 & 2 : Implémentation d'automates Automaton.h testAutomaton.c Makefile
2	18/09/17	CM 2 : Langages reconnaissables - Automates finis	TD 2 : Automates
3	25/09/17	CM/TD/TP annulés
4	02/10/17	CM/TD/TP annulés
5	09/10/17	CM 3 : Déterminisation	TD TP annulés
6	16/10/15	CM 4 : Théorème de Kleene	TD 3 : Déterminisation	TP 3 : Opérations régulières interpreteur.c
7	23/10/17	CM 5 : Théorème de Myhill Nerode	TD 4 : Théorème de Kleene	TP 4 : Elimination des transitions vides draw.c
8	30/10/17	Vacances Toussaint
9	06/11/17	CM 6 : Minimisation	TD 5 : Résiduels	TP 5 : Elimination des transitions vides (suite)
10	13/11/17	PARTIEL	TD 6 : Minimisation	TP 6,7 : Déterminisation set.c set.h
11	20/11/17	CM 7 : Grammaires	TD 7 : Grammaires	TP 6,7 : Déterminisation set.c set.h
12	27/11/17	CM 8 : Automates à pile	TD 8 : Automates à pile	TP 8 : Minimisation complete.c
13	04/12/17	CM 9 : Machines de Turing	TP 9	TP 10
14	11/12/17		EVALUATION TP

	PARTIEL	EXAMEN	PROJET
MAX	25%	50%	25%
MAX	0%	75%	25%

Pour l'évaluation, votre interpréteur doit tourner sur les machines de l'université et doit reconnaître la liste suivante de commandes :

elem i	crée un automate reconnaissant l'entier i
union	effectue l'union des deux automates en sommet de pile
concat	effectue la concaténation des deux automates en sommet de pile
kleene	effectue la fermeture de kleene de l'automate en sommet de pile
rmepsilon	elimine les transitions epsilon de l'automate en sommet de pile
deter	déterminise l'automate en sommet de pile
minimize	minimise l'automate en sommet de pile
prune	elimine les états non accessibles de l'automate en sommet de pile
affiche	affiche l'automate en sommet de pile au format ATT
draw	dessine l'automate en sommet de pile
quit	quitte l'interpréteur

base	elimination epsilon	determinise	minimise
ex10.cmd ex10.pdf	ex11.cmd ex11.pdf	ex12.cmd ex12.pdf	ex13.cmd ex13.pdf
ex20.cmd ex20.pdf	ex21.cmd ex21.pdf	ex22.cmd ex22.pdf	ex23.cmd ex23.pdf
ex30.cmd ex30.pdf	ex31.cmd ex31.pdf	ex32.cmd ex32.pdf	ex33.cmd ex33.pdf

Henri Garreta Le langage C
Alfred Aho, Jeffrey Ullman The Theory of Parsing, Translation and Compiling, Vol I : Parsing Prentice-Hall, 1972
John Hopcroft, Rajeev Motwani, Jeffrey Ullman Introduction to Automata Theory, Languages and Computation, 2ème édition Pearson Education International, 2001.
Michael Sipser Introduction to the Theory of Computation PWS Publishing Company, 1997.

Théorie des langages
	Organisation et contenu du cours
	Modalités de contrôle
	Evaluation du projet
	Machines de Turing
	Examens des années précédentes
	Bibliographie