CCP 2004 informatique

1 2Les calculatrices sont interdites. 1.2 Representation´ graphique d’un automateLes automates peuvent etreˆ represent´ es´ par un schema´ suivant les conventions :N.B. : Le candidat attachera la plus grande importance a` la clarte,´ a` la precision´ et a` la concisionde la redaction.´Si un candidat est amene´ a` reperer´ ce qui peut lui sembler etreˆ une erreur d’enonc´ e,´ il le signalera sur– les valeurs de la relation de transition sont represent´ ees´ par un graphe oriente´ dont les nœudssa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu’il a et´ e´ amene´ sont les etats´ et les aretesˆ sont les transitions ;a` prendre.– un etat´ initial est entoure´ d’un cercle i ;´ – un etat´ terminal est entoure´ d’un double cercle t ;PREAMBULE : Les deux parties qui composent ce sujet sont independantes´ et peuvent etreˆ traitees´ parles candidats dans un ordre quelconque.– un etat´ qui est a` la fois initial et terminal est entoure´ d’un triple cercle it ;– une areteˆ etiquet´ ee´ par le symbole e2 X va de l’etat´ o a` l’etat´ d si et seulement si (o;e;d)2 .Partie I : Automates et langagesExemple I.1 L’automateE = (Q;X;I;T; ) avec :1Le but de cet exercice est l’etude´ des propriet´ es´ des operations´ de deri´ vation a` gauche m :A et a`1droiteA:m d’un automate finiA selon un mot m. Q =fA;B;C;D;EgX =fa;bgI =fA;BgT =fD;Eg1 Automate fini =f(A;a;C);(A;b;D);(B;a;D);(B;b;B);(C;b;E);(D;a;C);(E;a;C)gPour simplifier les ...