TD3 - Automates et Langages - RICM

Un peu de programmation

Le but de ce TD est de mieux comprendre les algorithmes et les manipulations sur les automates vus en cours en écrivant les programmes. Pour ne pas se perdre dans les détails on utilise la téchnique de programmation "top-down" sans descendre trop bas. Les téchniques du module LP seront utiles. Pour certains problèmes vous verrez des méilleures solutions dans LP ultérieurement.

Problème 1. Test d'acceptation.

Etant donné un automate A et un mot w tester si le mot est accepté par l'automate. Ecrire les programmes pour les cas suivants:

Indications. Choisissez bien les structures de données. Utilisez les schémas de calcul des états atteignables vus en cours.

Exercice. Test de langage non-vide.

Etant donné un automate non-deterministe A tester est-ce qu'il accepte au moins un mot.

Problème 2. Les 2 manipulations...

Ecrire les programmes pour

Indication. Réutilisez les structures de données et les fonctions du problème 1.

TD1 TD2 TD4 TD5 TD7

Retour