Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

grammaires hors contexte

Th ?eorie des langages Grammaires Hors-Contexte Elise Bonzon http web mi parisdescartes fr bonzon elise bonzon parisdescartes fr Th ?eorie des langages CGrammaires Hors-Contexte Grammaires Hors-Contexte D ?e ?nitions Grammaires r ?eduites Grammaires propres Formes normales Th ?eorie des langages CGrammaires Hors-Contexte Grammaires Hors-Contexte D ?e ?nitions Grammaires r ?eduites Grammaires propres Formes normales Th ?eorie des langages CGrammaires Hors-Contexte Grammaire Hors-Contexte Grammaire Hors- Contexte ou alg ?ebrique Une grammaire G V ? P S est hors-contexte ou alg ?ebrique si V est un alphabet ? ? V est l ? ensemble des symboles terminaux V ? est l ? ensemble des symboles non terminaux S ?? V ? est le symbole de d ?epart P ? V ? ? V ? est l ? ensemble ?ni de r egles de production Th ?eorie des langages CGrammaires Hors-Contexte Grammaire Hors-Contexte Grammaire Hors- Contexte ou alg ?ebrique Une grammaire G V ? P S est hors-contexte ou alg ?ebrique si V est un alphabet ? ? V est l ? ensemble des symboles terminaux V ? est l ? ensemble des symboles non terminaux S ?? V ? est le symbole de d ?epart P ? V ? ? V ? est l ? ensemble ?ni de r egles de production Langage alg ?ebrique Un langage L est alg ?ebrique s ? il existe une grammaire alg ?ebrique telle que L G L Th ?eorie des langages CGrammaires Hors-Contexte Grammaire Hors-Contexte Cons ?equence Tout langage rationnel est alg ?ebrique ATTENTION la r ?eciproque est fausse Un langage alg ?ebrique non rationnel n ? est pas reconnu par un automate ?ni n ? est pas d ?ecrit par une expression r ?eguliere il n ? existe pas de grammaire r ?eguliere pour l ? engendrer Th ?eorie des langages CGrammaires Hors-Contexte Rappel hierarchie de Chomsky Type Pas de restriction Type Grammaires contextuelles ou sensibles au contro le Context-sensitive ? ? ? ? ?? V Type Grammaires hors-contexte Context-Free A ? ? Type Grammaires r ?egulieres ou lin ?eairesa droite A ? wB A B ?? V ? non terminaux A ? w w ?? ? ? terminaux Th ?eorie des langages CGrammaires Hors-Contexte Rappel hierarchie de Chomsky T R ?eguliers Automate ?ni T Context Free Automate a pile T Context sensitive Machine de Turing T Th ?eorie des langages CGrammaires Hors-Contexte Grammaire hors contexte exemple Soit G V ? P S avec ? a b V ? S Axiome S r egles de production S ? aSb S ? L G anbn n ? Th ?eorie des langages CGrammaires Hors-Contexte Grammaire hors contexte langage PASCAL instruction ? variable expression begin liste-instructions end if expression then instruction if expression then instruction else instruction case expression of liste-case end while expression do instruction repeat instruction until expression for varid liste-pour do instruction identi ?cateur -procedure identi ?cateur -procedure liste-expressions goto etiquette with liste-variables-record do instruction etiquette instruction Th ?eorie des langages CGrammaires Hors-Contexte Grammaire hors contexte langage PASCAL instruction ? variable expression begin liste-instructions