Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Grammaire contextuelle
Résumé
Une grammaire contextuelle est une grammaire formelle dans laquelle les substitutions d'un symbole non terminal sont soumises à la présence d'un contexte gauche et d'un contexte droit. Elles sont plus générales que les grammaires algébriques. Les langages formels engendrés par les grammaires contextuelles sont les langages contextuels. Ils sont reconnus par les automates linéairement bornés.
Les grammaires contextuelles ont été décrites par Noam Chomsky. Ce sont les grammaires de type 1 dans la hiérarchie de Chomsky. Elles peuvent servir à décrire la syntaxe de langages naturels où il apparaît qu'un mot est approprié dans un certain contexte, mais ne l'est pas par ailleurs.
Une grammaire formelle , (où est l'ensemble des variables ou symboles non terminaux et est l'alphabet terminal ou l'ensemble des symboles terminaux) est contextuelle si toutes les règles de sont de la forme
où , et sont des mots quelconques, avec non vide, et est une variable.
Ainsi, le remplacement de par se fait en présence du « contexte » .
Parfois, on permet la règle
où désigne le mot vide, sous réserve que n'apparaisse pas dans un membre droit de règle. Cette convention technique permet de considérer les langages contextuels comme un sur-ensemble des langages algébriques, sans devoir préciser que l'inclusion est limitée aux langages ne contenant pas le mot vide.
Une grammaire est croissante ou monotone si, pour toute règle , la longueur de
est inférieure ou égale à la longueur de . On sait transformer une grammaire croissante en une grammaire contextuelle (voir ci-dessous). Par conséquent,
Les langages engendrés par les grammaires croissantes sont exactement les langages contextuels ne contenant pas le mot vide.
Une grammaire est en forme normale de Kuroda si les règles sont de l'une des formes suivantes :
où sont des variables et est une lettre terminale. Les grammaires en forme normale de Kuroda sont croissantes. Réciproquement, on sait transformer une grammaire croissante en une grammaire en forme normale de Kuroda.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.