cours-I5

Universite d’Aix-Marseille III - Licence Math-Info, 2eme anneeI5 : Langages formels, automates et grammaires - Notes de coursDans ce cours, nous etudierons les langages formels. Nous verrons deux manieres de les modeliser: lesmachines abstraites (automates et machines de Turing) et les grammaires formelles.1 Inter^et des langages formels en informatique theoriqueUne categorie fondamentale de problemes que l’on se pose en informatique regroupe les problemes dedecision. Ils correspondent a une question dont la reponse doit ^etre "oui" ou "non" du type "est-ce que ceciest une solution a tel probleme?". Ex: est-ce que cette suite de chi res represente un nombre premier? Estce que cette suite de caracteres correspond a un programme C correctement forme? Plus formellement, defa con generale, la question a laquelle repond un probleme de decision est "Est-ce que cette suite de symbolesfait partie de l’ensemble des suites de symboles qui correspondent a une solution de mon probleme?".Un langage formel se de nit simplement comme un ensemble de suites de symboles. On peut alorsconsiderer qu’un langage formel contient l’ensemble des suites de symboles pour lesquelles la reponse d’unprobleme de decision est "oui". Si on considere l’ensemble de tous les langages possibles, nous avons a aire al’ensemble des ensembles de solutions de tous les problemes possibles. La question est alors de savoir si, quelque soit le langage formel, il est ...