Remerciez-le!

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

ricm3 ex corrige Nom Prénom Groupe ou Numéro d'étudiant si l'examen est anonyme RICM Automates et Grammaires Durée h sans documents Tous les appareils électroniques sont interdits à l'exception des montres Le barème est donné à titre indicatif Le sujet co

Nom Prénom Groupe ou Numéro d'étudiant si l'examen est anonyme RICM Automates et Grammaires Durée h sans documents Tous les appareils électroniques sont interdits à l'exception des montres Le barème est donné à titre indicatif Le sujet comporte exercices indépendants Il est noté sur Répondez sur votre copie sauf pour les questions avec pointillés N'oubliez pas de mettre votre nom ou votre numéro d'étudiant sur le sujet Commencez par lire tout le sujet pour repérer les questions faciles Exercice Reconnaissance d'un terme par un automate d'arbre - pt min On considère l'alphabet ? a f g C et l'automate d'arbre dé ni par les transitions suivantes F F F F F F F F a ?? ? Qa a F F F F F F F F F F F F F F F F g Qg x ?? ? Qg g x F F F F F F F F g Qa x ?? ? Qg g x F F F F F F F F F F F F F F f Qg x Qg y ?? ? Qf f x y o? Qa Qg Qf représentent les états de l'automate d'arbre Qf est l'unique état accepteur x et y sont des variables Q pt Donnez un terme qui n'est pas reconnu par l'automate solution a conduit à Qa a et l'état Qa n'est pas accepteur ou bien f a a conduit à f Qa a Qa a et aucune règle de dérivation ne permet de poursuivre l'exécution C pt Q Donnez l'exécution qui permet de montrer que le terme f g a g a est reconnu par l'automate solution f g a g a ? ? f g Qa a g Qa a ? ? f Qg g a Qg g a ? Qf f g a g a On a lu tout le terme et Qf est un état accepteur Exercice Expressions régulières pt min B Q On note L l'ensemble des lettres minuscules et C l'ensemble des chi res Donnez l'expression pt régulière qui décrit les noms de variables formés sur l'alphabet ? C L ?? C ?? - sachant qu'un identi cateur est formé d'au moins un caractère et doit commencer par un lettre ou un souligné id d ef L - ? ? C Dé nition de l'opérateur ?? sur les expressions régulières Q pt On note L e le langage associé à l'expression régulière e Soit e et e deux expressions C régulières dé nissez l'opérateur privé de notée - L e ?? e d ef L e L e L e ?? L e à l'aide des opérateurs ensemblistes ?? et ?? Q pt Soit A l'automate associé à e et A l'automate associé à e expliquez comment construire l'automate associé à e ?? e L e ?? e L e ?? L e L A ?? L A L A ? A C Donc l'automate associé à e ?? e est A ? A C Q pt Donnez l'expression régulière