Remerciez-le!

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

Automates expressions regulieres algo de moore

Langages r ?eguliers Langages reconnaissables Ensembles r ?eguliers Grammaires de r ?e ?ecriture Une grammaire de r ?e ?ecriture est un -uplet N ? P S ou N est un ensemble de symboles non terminaux appel ?e l ? alphabet non terminal ? est un ensemble de symboles terminaux appel ?e l ? alphabet terminal tel que N et ? soient disjoints P est un sous ensemble ?ni de N ?? ? ? N N ?? ? ? ? N ?? ? ? un ?el ?ement ? de P que l ? on note ? ? est appel ?e une regle de production ou regle de r ?e ?ecriture est appel ?e partie gauche de la regle ? est appel ?e partie droite de la r egle S est un ?el ?ement de N appel ?e l ? axiome de la grammaire Alexis Nasr Compilation CLangages r ?eguliers Langages reconnaissables Ensembles r ?eguliers Regles r ?egulieres et grammaires r ?egulieres Une regle est r ?eguliere a gauche si et seulement si elle est de la forme A ? xB ou A ? x avec A B ?? N et x ?? ? Une regle est r ?eguliere a droite si et seulement si elle est de la forme A ? Bx ou A ? x avec A B ?? N et x ?? ? Une grammaire est r ?eguliere si elle est r ?eguliere a droite ou r ?eguliere a gauche Une grammaire est r ?egulierea gauche si toutes ses regles sont r ?egulieres a gauche et une grammaire est r ?eguliere adroite si toutes ses regles sont r ?egulieres a droite Alexis Nasr Compilation CLangages r ?eguliers Langages reconnaissables Ensembles r ?eguliers Proto- phrases d ? une grammaire Les proto-phrases d ? une grammaire G N ? P S sont des mots construits sur l ? alphabet ? ?? N on les d ?e ?nit r ?ecursivement de la fac on suivante S est une proto-phrase de G si ? ? est une proto- phrase de G et ? ? ? ?? P alors ? ? est une proto-phrase de G Une proto- phrase de G ne contenant aucun symbole non terminal est appel ?e un mot g ?en ?er ?e par G Le langage g ?en ?er ?e par G not ?e L G est l ? ensemble des mots g ?en ?er ?es par G Alexis Nasr Compilation CD ?erivation Langages r ?eguliers Langages reconnaissables Ensembles r ?eguliers L ? op ?eration qui consiste a g ?en ?erer une proto-phrase ? ?a partir d ? une proto-phrase ? ? et d ? une regle de production r de la forme ? ? ? est appel ?ee l ? op ?eration de d ?erivation Elle se notea l ? aide d ? une double eche ? ? ?? ? ? On note k ?? ? pour indiquer que ? se d ?erive de en k ?etapes On d ?e ?nit aussi les deux notations ?? et ? ??