TD 1 Langages rationnels PDF 16 sept. 2015 (g) l'

Les lettres de l'alphabet. Soratra : Ny litera : “o” “i”

Petits mots contenant une lettre « chère » (J K Q W X Y Z)

Petits mots contenant une lettre « chère » (J K Q W X Y Z). Mots et définitions extraits du Dictionnaire Officiel du Scrabble 5èmeédition Larousse

La lettre x se prononce [gz].

** Écris un mot de la même famille contenant la lettre x: a Utilise des mots contenant la lettre xcomme anxieux complexe

Des-mots-contenant-la-lettre-m.pdf

Page 1. Des mots contenant la lettre m. Page 2.

FRANÇAIS

Il a des difficultés à lire des mots contenant des lettres muettes finales autres que « e. » (début fort

Concept du jeu : Préparation : Déroulement de la partie :

de 3 lettres 80 mots de 2 lettres et 3 mots de 1 lettre. Y : ay

Des-mots-contenant-la-lettre-A.pdf

Page 1. Des mots contenant la lettre a. Page 2.

Corrigé des exercices

Le langage des mots contenant au moins une fois la lettre a : q0 q1 a b ab. 2. Le langage des mots contenant au plus une fois la lettre a : q0 q1 a b b. 3

Tom Pousse

La lettre G Range les mots contenant la lettre G aux bons endroits : Trouve des mots de la même famille pour justifier le G muet des mots : poing long

Les corrigés

Retrouve dans cette suite de lettres 5 mots contenant le phonème[ g ] et écris-les: firtugosserméglisestapumalgrétobunegauchehaliégaufreve. - gosse - église

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 à ...

1. Les commandes grep et find 1.1 Les expressions régulières 1.2

Permet d'obtenir les lignes contenant la chaîne de caractère Brest soit : à un certain critère (par exemple chaîne contenant des lettres minuscules.

Séquence de travail sur Les valeurs de la lettre h

Mémoriser des mots contenant la lettre h. Séance 1 :Résolution d'un problème orthographique : à quoi sert la lettre H ? Objectifs :.

Corrigé des exercices

3. Le langage des mots contenant un nombre pair de fois la lettre a : q0 q1 a b b a. 4. Le langage des mots admettant aba pour facteur :.

JEUX dECRITURE

Les logogriphes sont des mots cachés à l'intérieur des autres. On choisit un mot et on demande aux enfants de composer d'autres mots avec les lettres du mot

Les corrigés

Retrouve dans cette suite de lettres 5 mots contenant le phonème[ g ] et Ecris les mots avec la bonne graphie « g » ou « ge » pour entendre le phonème ...

Les valeurs de la lettre « c » Séances 1 et 2: résolution dun

Construction d'un classement par groupe : « Comment peut-on classer les mots contenant la lettre « c » ? » - Réactivation et si besoin relecture du texte 2

Synopsis (scope and sequence) des émissions radiophoniques

Les mots contenant les sons étudiés Ny teny ampiasaina ahitana ny feo : [o] [i]

Séquence sur les valeurs de la lettre « t »

contenant la lettre « t » ? » Remarques : -. Ne pas faire lire les mots au tableau collectivement pour favoriser la capacité des élèves à bien découper.

5e année Proposition 1 des difficultés orthographiques à retenir.docx

Bloc 8 - Mots contenant le son /in/: graphies in im

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] TD 1 Langages rationnels 16 sept. 2015 (g) l'

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,