Remerciez-le!

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

Lgg regulier Contenu ? Théorie des langages formels ? Langages naturels VS langages formels ? Dé ?nitions propriétés et opérations sur les langages ? Génération VS reconnaissance ? Hiérarchie de Chomsky ? Langages réguliers ? Dé ?nitions et propriétés ? T

Contenu ? Théorie des langages formels ? Langages naturels VS langages formels ? Dé ?nitions propriétés et opérations sur les langages ? Génération VS reconnaissance ? Hiérarchie de Chomsky ? Langages réguliers ? Dé ?nitions et propriétés ? Trois représentations grammaires régulières expressions régulières automates à états ?nis ? Manipulation déterminisation minimisation changement de représentation ? Décider si un langage est régulier Langages réguliers ? Dé ?nition inductive des langages réguliers Lreg ? Base ? ?? ??a ??LlpLrheregag bet ? ??x ?? ? x ??Lreg ? Induction ?? L L ??Lreg L ??L L L et L ??Lreg ? Théorème Tout langage ?ni est régulier ? Autres dé ?nitions ? engendré par une grammaire régulière ? reconnu par un automate à états ?nis ? dé ?ni par une expression régulière Question équivalence de toutes ces dé ?nitions Langages réguliers Langages réguliers Préservation clôture de la régularité par ? Opérations ensemblistes ? Union par dé ?nition ? Complémentation admis ? Intersection L ??L L c ??L c c ? Di ?érence L -L L ??L c ? Opérations algébriques ? Concaténation par dé ?nition ? Itération par dé ?nition ? Puissance L n L L L ? L Langages réguliers Grammaires régulières ? Rappel G VT VN S R est régulière ssi ?? ? ? ??R ??VN et ? ?? VT VN ??VT ? Théorème Langages engendrés par grammaires régulières L Greg Langages réguliers Lreg Preuve Montrer Lreg ? L Greg en construisant des grammaires générant tout langage véri ?ant la dé ?nition inductive Montrer L Greg ? Lreg en dé ?nissant le langage engendré par une grammaire régulière par la dé ?nition inductive Langages réguliers Lreg ? L Greg ? Base ? ? engendré par ? S S S ?S ? engendré par ? S S S ? ? x engendré par x S S S ?x ? Induction Soient L ?G VT VN S R et L ?G VT VN S R ? L ??L ? G VTR ?? ??VRT ?? V SN ? ??SV N S ?? S S ? L L ? G VT ?? ??V T ? wVN S ?? V N ? Sw ?? R ? ww ?? XV ??T R ??XR ?? V N ? L ? G VT V N ? ??w S S S R ? w ?? ?? SR ? Sw ?? V T ?? Attention type G ?? si S ? ??R ou S ? ??R Langages réguliers L Greg ? Lreg Soit G VT VN S R une grammaire régulière ? Pour chaque z ??VN on dé ?nit Lz le langage des mots engendrés à partir de z ? Soit z ? v v ? vn w z w z ? wmzm ??R l ? ensemble des règles ayant pour partie gauche le symbole non-terminal z avec vi ??VT wi ??VT et zi ??VN ? Alors Lz v ?? v ?? ? ?? vn ?? w Lz ?? w Lz ?? ? ?? wm Lzm Lz se dé ?nit