Colloque

Grammaires matricielles et classe de langages formels

Jean Friant

Membre a labase

Jean Friant

Résumé du colloque

Diverses classes de grammaires sont définies et comparées au point de vue de leur capacité générative aux classes définies par N. Chomsky, ainsi qu'à celles introduites plus récemment par D. Rosenkrantz ("Programmed Grammars") et S. Greibach et J. Hopcroft ("Scattered content grammars"). Ces derniers modèles et ceux présentés ici se différencient de ceux de Chomsky par le fait essentiellement que des contraintes sont imposées à l'ordre d'application des règles lors d'une dérivation. Diverses propriétés de fermeture sont établies.