Grammaires sans contexte

Cette séance de cours présente les grammaires sans contexte comme un formalisme plus expressif que les automates finis et les expressions régulières, permettant la description de langages sans contexte. L'instructeur explique l'équivalence entre les automates pushdown et les grammaires sans contexte, détaillant les composants et les transitions des automates pushdown. La séance de cours couvre la définition des grammaires sans contexte, y compris les terminaux, les non-terminaux et les règles. Il explore le concept de langages sans contexte et comment vérifier si un mot appartient à la langue d'une grammaire en utilisant des algorithmes comme l'algorithme CYK. En outre, la séance de cours plonge dans le lemme de pompage pour les langues sans contexte, démontrant comment trouver une sous-chaîne répétée dans une langue. La hiérarchie des types de grammaire est discutée, mettant en évidence les restrictions et l'expressivité des différents niveaux de grammaire, menant à des grammaires de type 0, qui n'ont aucune restriction sur l'application des règles.