TD Langages Formels
Travaux dirigés
- Langages reconnaissables/rationnels
- Minimisation
- Automates d'arbres (problèmes de décision, langages déterministes descendants)
- Automates d'arbres (itération, alternance)
- Reconnaissance par morphisme, minimisation des automates d'arbres, homomorphismes d'arbres
- Grammaires syntagmatiques
- Grammaires algébriques : langage local d'arbres, lemme d'Ogden, ALGOL 60
- Formes normales, théorème de Chomsky-Schützenberger, analyse syntaxique
- Automates à pile
- Langages déterministes, langages simples
- Fonctions séquentielles
- Minimisation de fonctions séquentielles
- Grammaires LL(k)
- Grammaires LR(k), SLR(k), LALR(k)
Devoirs
- Automates et XML
- Grammaires de quotients