Systèmes Formels

But

Le but est d'introduire aux fondements de l'informatique et d'introduire à la compilation.

Evaluation

Cette UE compte pour 2 crédits ECTS.

Objectifs

Ils sont mis à jour régulièrement :

1. Savoir définir mot et langage
2. Savoir écrire une expression réguliére simple
3. Savoir définir un ensemble dénombrable
4. Savoir définir une bijection entre deux ensembles dénombrables
5. Savoir montrer qu'un ensemble est non dénombrable
6. Connaitre le cardinal de l'ensemble des partis d'un ensemble fini
7. Connaitre les opérations algébriques sur les langages
8. Savoir définir langage rationnel
9. Savoir définir le langage reconnu par un automate fini déterministe
10. Savoir construire un automate fini déterministe reconnaissant un langage
11. Savoir écrire l'expression régulière du langage reconnu par un automate fini déterministe
12. Connaitre la définition d'un automate fini non-déternimiste
13. Savoir déterminiser un automate
14. Savoir construire un automate à état fini reconnaissant un language rationnel simple
15. Connaître le théorème de Kleene
16. Savoir définir un automate fini déterministe
17. Connaitre le principe de recherche de motif par automate
18. Connaître la définition d'une grammaire
19. Savoir dessiner l'arbre de dérivation d'un mot selon une grammaire
20. Connaitre la définition d'une grammaire régulière
21. Savoir concevoir un automate fini reconnaissant le langage d'une grammaire régulière
22. Savoir définir une grammaire engendrant le même langage qu'un automate fini déterministe
23. Connaitre la classification de Chomsky des langages
24. Connaitre les définitions de clôture
25. Savoir les propriétés de clôture des langages rationnels
26. Connaitre le lemme de l'étoile
27. Savoir que le langage 0^n1^n n'est pas rationnel
28. Savoir démontrer qu'un langage n'est pas rationnel par le lemme de l'étoile
29. Savoir démontrer qu'un langage n'est pas rationnel en utilisant les propriétés de clôture
30. Savoir programmer un système de réécriture
31. Savoir représenter graphiquement un mot issu d'un système de réécriture
32. Connaitre la définition d'une machine de Turing
33. Savoir exécuter une machine de Turing
34. Savoir définir le langage reconnu par une machine de Turing
35. Savoir définir la fonction calculée par une machine de Turing
36. Savoir définir une machine de Turing pour reconnaître un langage ou calculer une fonction
37. Connaitre la thèse de Church-Turing
38. Savoir que le problème de l'arrêt est non calculable

Supports des cours et des travaux

Voici l'ensemble des supports des cours et des émoncés des travaux.

Bibliographie

Quelques repères biblio- /webo- graphiques qui vont se complèter au fur et à mesure :

• Denis Robilliard, Université du Littoral Côte d'Opale,
• Sandrine Julia, Université de Nice Sophia Antipolis.

Horaires

7,5h de CM, et de 7,5h de TD.


Consulter l'emploi du master : edt