[PDF] TD 1 Langages rationnels PDF TD1.lrationnels.corrected.pdf

16 sept 2015 · (g) l'ensemble des mots contenant au moins un a ; (h) l'ensemble des mots comportant au moins 3 lettres et dont la troisième lettre à partir

- Ecrire une phrase, chaque mot contenant la même lettre (on doit l'entendre): " Les papillons sautillent vivement sur les tulipes du massif " - Ecrire la plus grande

[PDF] Exercices

3) Change la première lettre et fais un autre mot : une maille de la 9) Je remets en ordre les lettres pour former des mots contenant le son [J] : t m é r e

[PDF] Les corrigés - Le Petit Journal des Profs

Retrouve dans cette suite de lettres, 5 mots contenant le phonème[ g ] et écris-les : commun de la même famille que le mot en gras et contenant la lettre « g » :

[PDF] Livret dexercices période 1 - Le Petit Journal des Profs

Utilise les syllabes pour former 5 mots contenant le phonème [I]: jam re bon Trouve les adjectifs correspondant à la définition et contenant la lettre c : a) C'est

[PDF] Liste de mots (contenant des mots fréquents), avec leur - Free

Liste de mots (contenant des mots fréquents), avec leur anagramme 3 lettres 4 lettres 5 lettres 6 lettres 7 lettres nom mon porte opter maison aimons cas sac

[PDF] TD 1 Langages rationnels

16 sept 2015 · (g) l'ensemble des mots contenant au moins un a ; (h) l'ensemble des mots comportant au moins 3 lettres et dont la troisième lettre à partir

[PDF] Livret dexercices corrigés

ré ter 9 *** Complète chacune de ces phrases avec un mot contenant le phonème [õ] : Écris le mot terminé par la lettre muette t de la famille de chaque mot :

[PDF] Exercice 1

Combien y a-t-il de mots de longueur p 1 sur un alphabet à n lettres ? 2 contenant au moins une occurrence d'une lettre donnée a ? 3 contenant exactement

[PDF] Fiche 02 : Langage rationnel Automate Fini Déterministe - LISIC

6 l'ensemble des mots contenant au moins un b 11 l'ensemble des mots comportant au moins 3 lettres et dont la troisi`eme lettre `a partir de la fin est un a ou

TD 1 Langages rationnels

Timothée Bernard (timothee.bernard@ens-lyon.org)

16 septembre 2015

1. Soit A=fa;b;cg. Pour chacun des langages suivants, donner un automate fini déterministe (AFD) le reconnaissant : (a) l"ensem bledes mots don tla longu eurest un m ultipled e3 ;

Solution:1start23a,b,ca,b,c

a,b,c (b) l"ensem bledes mots dans lesquels le mo tifab, s"il apparaît, est suivi deccc; (c) l"ensem bledes mots se terminan tp arb;

Solution:1start2a,c

b a,cb (d) l"ensem bledes mots ne se terminan tpas par b;

Solution:1start2a,c

b a,cb (e) l"ensem bledes mots con tenantexactemen tun b;

Solution:1start2a,c

ba,c (f) l"ensem bledes mots ne con tenantaucun b; 1

Solution:1starta,c

(g) l"ensem bledes mots con tenantau moins un a; (h) l"ensem bledes mots comp ortantau moins 3 lettres et don tla troisième lettre à parti r de la fin est unaou unc;

Solution:

Soit déterminiser l" automatesuiv ant: 1start234a,b,c a ca,b,ca,b,c soit directemen tcon struireun automate à 8 éta ts,c hacuncorresp ondant à une distribution desaetcdans les 3 dernières lettres lues (avec des transitions bien choisies évidemment).(i)l"ensem bledes mots de longueur paire ; (j) l"ensem bledes mots se terminan tpar bc. 2. Prop oserun aut omateet une expression rat ionnellep ourle langa gede tous les mots de fa;b;cgdontcacest un sous-mot1.

Solution:1start234a,b,c

caa,b,c ca,b,ca,b,c

Expression rationnelle :(a|b|c)*c(a|b|c)*a(a|b|c)*c(a|b|c)*3.Déterminiser l"automate suiv anten appliquan tl"algorit hmevu en cours

2:1start25

34a
ab b acc ba

1. Unsous-motdeuest une sous-suite de lettres - non nécessairement contiguë - deu. À distinguer d"un

facteur. Exemple :pisest un sous-mot deproduits.

2. poly p.9

" Se convaincre » que l"automate déterminisé reconnaît le même langage en testant l"appar-

tenance au langage d"un petit nombre de mots.

Solution:1start2;32;432;552;3;5ac

ba abc ab abc 4.

Soit l"expression rationnelle (aajb)c.

(a) Utiliser la méth odevue en cours p ourconstruire un automate recon naissantle même langage 3.

Solution:1start2345

678910

aa bc (b) Á parti rde l"automate, prop oserune gram mairerégulière engend rantle même langage.

Solution:

1!aS3jbS7

S 3!aS5 S

5!cS10

7!cS10

S 10! (N"oubliez pas que les règles singulières sont interdites dans une grammaire régu- lière.)(c)Donner un arbre syn taxiquea vecla grammaire précé dentep ourle mot aac. 5. Soit A=fa;b;cg, considérons l"expression rationnelle(ajbc).3. poly p.18 3 (a)Utiliser l amétho devue en cours p ourconstruire un AF reconn aissantle même langage 4.

Solution:1start2345

6789
a bc (b)

Éliminer les -transitions5.

Solution:

On donne+

1!2 , 3 , 6

2!3 ,6

4!5 , 1 , 2 , 3 , 6

5!1 , 2 , 3 , 6

7!8

9!5 , 1 , 2 , 3 , 6Solution:

0abc

1 (i/f)47

247
34

4 (f)47

5 (f)47

67
79
89

9 (f)47

(i)!Etat initial (a)!Etat final On remarque que les états 2, 3, 5, 6 et 8 ne sont plus accessibles. Ils ne sont donc plus utiles et on peut les retirer.Solution:

4. poly p.18

5. poly p.7

1start4

79a
ba b ca b (c)

Déterminiser l"automate résultan t

6. Solution:On a de la chance (mais ce n"est pas nécessairement le cas) : on peut vérifier facilement que l"automate est déjà déterministe.(d)Compléter

7puis minimiser8l"AFD.

Solution:1;4;9start70a

bc a;b ca;b;c (e) Construire l agrammaire régulière (à droite)

9reconnaissant le même langage que

l"AFDC.

Solution:

1!aS1jbS7jcS0j

7!cS1jaS0jbS0

0!aS0jbS0jcS0

(Il est cependant aisé de montrer qu"il n"existe aucun chemin de l"état 0 vers un état final, on peut donc supprimer cet état et utiliser l"algorithme pour produire

une grammaire plus simple.)6.Soit la grammaire suiv ante: G1= (fa;bg;fSg;S;fS!aSbSjbSaSjg). Quel est le langage

Lreconnu ? (Le prouver par double inclusion, c-à-d en montrant d"une part que tout mot reconnu appartient àLet d"autre part que tout mot deLest reconnu.) Solution:Il s"agit de l"ensemble des mots contenant autant deaque deb. Ce langage n"est en fait pas régulier (on peut le montrer avec le lemme de pompage)!6. poly p.9

7. poly p.6

8. poly p.10

9. poly p.17

5 Montrer que tous les mots contenant autant deaque debsont bien générés est un peu

technique mais très intéressant : on peut procéder par récurrence sur la taille des mots.7.Soit Lun langage rationnel, en utilisant des considérations sur les automates montrer que :

(a) l"ensem bledes préfixes de L,L0=fuj9v;uv2Lgest aussi rationnel; (b) l"ensem bledes suffixes de L,L00=fvj9u;uv2Lgest aussi rationnel.

Solution:SoitLun langage régulier,

soitAun AF reconnaissantL, soit A0l"AF construit à partir deAoù tous les états sont acceptants : on peut montrer facilement queA0reconnaitL0, ainsiL0est régulier; soit A00l"AF construit à partir deAoù tous les états sont initiaux : on peut montrer facilement queA00reconnaitL00, ainsiL00est régulier.6quotesdbs_dbs19.pdfusesText_25

[PDF] [PDF] TD 1 Langages rationnels

TD 1 Langages rationnels

16 septembre 2015

Solution:1start23a,b,ca,b,c

Solution:1start2a,c

Solution:1start2a,c

Solution:1start2a,c

Solution:1starta,c

Solution:

Solution:1start234a,b,c

2:1start25

1. Unsous-motdeuest une sous-suite de lettres - non nécessairement contiguë - deu. À distinguer d"un

2. poly p.9

Solution:1start2;32;432;552;3;5ac

Soit l"expression rationnelle (aajb)c.

Solution:1start2345

678910

Solution:

1!aS3jbS7

5!cS10

7!cS10

Solution:1start2345

Éliminer les -transitions5.

Solution:

On donne+

1!2 , 3 , 6

2!3 ,6

4!5 , 1 , 2 , 3 , 6

5!1 , 2 , 3 , 6

9!5 , 1 , 2 , 3 , 6Solution:

1 (i/f)47

4 (f)47

5 (f)47

9 (f)47

4. poly p.18

5. poly p.7

1start4

Déterminiser l"automate résultan t

7puis minimiser8l"AFD.

Solution:1;4;9start70a

9reconnaissant le même langage que

Solution:

1!aS1jbS7jcS0j

7!cS1jaS0jbS0

0!aS0jbS0jcS0

7. poly p.6

8. poly p.10

9. poly p.17

Solution:SoitLun langage régulier,