Langages algébriques

Plan détaillé

Cours n° 1 : grammaires algébriques

(cf. [Aut87])

• Grammaires
  • définition et exemples
  • grammaires réduites
  • grammaire propres
  • système d'équations associé à une grammaire
  • arbres de dérivation
  • ambiguïté
  • forme normale quadratique
• Lemmes d'itérations
  • lemmes d'Ogden
  • application à L = { aⁿbⁿcⁿ | n ≥ 0 }
  • application à l'ambiguïté de L = { aⁿbⁿc^* | n ≥ 0 } ∪ { a^*bⁿcⁿ | n ≥ 0 }

Cours n° 2 : automates à pile

• Propriétés de clôture des langages algébriques
  • opérations rationnelles
  • grammaires linéaires droites (gauches)
  • substitution algébrique
  • morphisme alphabétique inverse
  • intersection avec un rationnel
  • théorème de Chomsky-Schützenberger
• Forme normale de Greibach
• Automates à pile
  • définitions et exemple
  • différents modes d'acceptation
  • équivalence avec les grammaires
• Automates déterministes