Corrigé des exercices PDF 3. Le langage des mots

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

Chapitre 4option informatique

Corrigé des exercices

Automates finis déterministes

Exercice 1

1. Le lang agedes mots con tenanta umoins une f oisla lettre a:q 0q

1aba;b

2. Le lang agedes mots con tenanta upl usune f oisla lettre a:q 0q 1abb 3. Le lang agedes mots con tenantun nombre pair de f oisla lettre a:q 0q 1abb a 4.

Le lang agedes mots admettan tabapour facteur :q

0q 1q 2q 3aba ba ba;b 5.

Le lang agedes mots admettan tabapour sous-mot :q

0q 1q 2q 3aba baba;b

Exercice 2Posonsn= 2p+ravecr2 f0;1g; alors :

p0 mod 5 =)nrmod 5p3 mod 5 =)n1+rmod 5 p1 mod 5 =)n2+rmod 5p4 mod 5 =)n3+rmod 5 p2 mod 5 =)n4+rmod 5

D"où l"automate :

http://info-llg.fr

4.2option informatiqueq

0q 1q 2q 3q 410
01 010 10

1Pour lire les entiers à partir du bit de poids le plus faible, il suffit de considérer l"automate transposé, c"est-à-dire

celui obtenu en inversant l"ordre des transitions et en échangeant états initiaux et états finaux. En général, la

transposée d"un automate déterministe est non déterministe, mais l"automate ci-dessus fait exception.q

0q 1q 2q 3q 410
01 010 10 1

Exercice 3

Il y a trois types de mots dans ce langage : ceux qui contiennent au moins unaet unbavant le

dernier caractère (étatq6), ceux qui ne contiennent que desaet qui sont de longueur au moins 2 (étatq3), ceux

qui ne contiennent que desbet qui sont de longueur au moins 2 (étatq5).q 0q 1q 2q 3q 4q 5q 6a ba b a ba b a;b a ba;b

Exercice 4

Les mots deL0sont les mots qui commencent par 1 et qui comportent au moins un 0 dans leur écriture.

D"où l"automate :

Corrigé des exercices4.3q

0q 1q 211

00;12.Les mots de E son treconn uspar l" automate:

q 0q 1q 21
01 0

3.NotonsL1le langage dénoté par01etL2le langage dénoté par(10). AlorsS=EL1L2doncSest reconnu

par l"automate :q 0q 1q 2q 3q 41
01 011 0

Exercice 5On définit deux suites (Ri) et (Si) de parties de Q en posant R0=fq0g, S0= F et pour touti2N:

R i+1= Ri[nq2Qil existe une transition d"un élément de Riàqo S i+1= Si[nq2Qil existe une transition deqà un élément de Sio

Ces deux suites sont croissantes dansQfini donc sont stationnaires. Leurs limitesRetSsont atteintes dès lors

que deux termes consécutifs sont égaux et dans ce casRest l"ensemble des états accessibles etSl"ensemble

des états co-accessibles. Il suffit dès lors de supprimer les états qui n"appartiennent pas àR\Sainsi que les

transitions dans lesquelles ces états interviennent pour obtenir l"automate émondé demandé.

Commençons par une fonction qui détermine les états accessibles en suivant l"algorithme exposé ci-dessus :letaccessible a =

let rec aux1 b =function | []> b | ((i, _), j)::q when mem i b &¬mem j b> aux1 (j::b) q | _::q> aux1 b q andaux2 b =letbb = aux1 b a.Deltain ifb = bbthenbelseaux2 bb inaux2 [a.Start] ;;On détermine de même les états co-accessibles : http://info-llg.fr

4.4option informatiqueletcoaccessible a =

let rec aux1 c =function | []> c | ((i, _), j)::q when mem j c &¬mem i c> aux1 (i::c) q | _::q> aux1 c q andaux2 c =letcc = aux1 c a.Deltain ifc = ccthencelseaux2 cc inaux2 a.Accept ;;Il reste à émonder l"automate : letemonde a = lete = intersect (accessible a) (coaccessible a)in let rec aux =function | ((i, _), j)::q whennotmem i e ||notmem j e> aux q | t::q> t::(aux q)

in{Start = a.Start; Accept = intersect a.Accept e; Delta = aux a.Delta} ;;Automates non déterministes

Exercice 6La déterminisation du premier automate conduit au résultat : 0a b fq0gfq0g fq0;q1gfq0;q1gfq0;q2g fq0;q1;q2gfq0;q2gfq0;q2g fq0;q1;q2gfq0;q1;q2gfq0;q2g fq0;q1;q2gq 00q 01q 02q 03a ba ba b ba La déterminisation du second automate conduit au résultat : 0a b fq0gfq1g fq2gfq1gfq1g fq0;q2gfq2gfq2g fq0gfq0;q2gfq1;q2g fq0;q2gfq1;q2gfq1;q2g fq0;q2gq 00q 01q 02q 03q 04a ba b b ab a ab

Corrigé des exercices4.5

Exercice 7Seules quatre configurations sont possibles : les qua trev erresson ttous dans le même sens (configur ationq0); trois v erresson tdans un sens et le qua trièmedans l" autresens (configur ationq1); deux v erresv oisinsson tdans un sens et les deux a utresdans l" autresens (configur ationq2); deux v erresopposés son tdans un sens et les deux a utresdans l" autresens (configur ationq3).

On désigne par la lettre :

-ale fait de changer l"orientation d"un des quatre verres; -ble fait de changer l"orientation de deux verres voisins; -cle fait de changer l"orientation de deux verres opposés. Le jeu peut alors être représenté par l"automate non déterministe suivant :q 0q 1q 2q 3aa ba bcb;c c Sa déterminisation conduit à l"automate suivant : 0123
12012

013010230212030a;b

c a ca c ba cab;c bcacbb;c acac

babOn constate que la succession de mouvementcbcacbcconduit nécessairement à une position gagnante pour le

barman.

Exercice 8T

(A)et doncA0=D(T(A))reconnait l"image miroir du langage reconnu parA, doncA00reconnait le même langage que A; il est équivalent à A.

On obtient pour A

0l"automate :

http://info-llg.fr

4.6option informatiqueq

00q 01q 02q 03q 04q 05q 06a ba b ba bb a bba et pour A

00l"automate :q

000q 001q 002ab a;bb a

Exercice 9L"automate non déterministe :q

0q 1q 2q 3q 4a;b abbaa;b se déterminise en : 0a b

fq0gfq0;q1g fq0gfq0;q1gfq0;q1g fq0;q2gfq0;q2gfq0;q1g fq0;q3gfq0;q3gfq0;q1;q4g fq0gfq0;q1;q4gfq0;q1;q4g fq0;q4gfq0;q4gfq0;q1;q4g fq0;q4gq

00q 01q 02q 03q 04q 05b aa b aba ba ba b On notera que l"étatq05peut être supprimé sans changer le langage reconnu par cet automate. L"algorithme KMP consiste à considérer les états et transitions suivants :a b "a"aa ab aba abb abbabba"abbaa ab

Corrigé des exercices4.7

puis à transformer l"état acceptant (abba) en puit :"aababbabbab aa b aba ba;b

Théorème deKleene

Exercice 10On commence par se débarrasser du symbole": l"expression rationnelle est équivalente à

(a+c)abb+(a+c). On la linéarise pour obtenir un langage local :(c1+c2)c3c4c5+(c6+c7), avecP=fc1;c2;c3;c6;c7g,

S =fc5;c6;c7get F =fc21;c22;c1c2;c2c1;c1c3;c2c3;c3c4;c4c5;c26;c27;c6c7;c7c6g.

On déduit de l"automate local qui en résulte l"automate deGlushkovde l"expression rationnelle en supprimant

le marquage des transitions :c 0c 3c 4c 5c 2c 1c 6c

7acaac

c aaaa cb bc aa c

On notera que puisque"appartient au langagec0est un état acceptant. Sa déterminisation fournit l"automate

suivant :q 0q 1q 2q 3q 4a ca cb cab Exercice 11L"automate suivant reconnait le langage L=nm2jmja0 mod 3o: http://info-llg.fr

4.8option informatiqueq

0q 1q 2ab ab a b

On lui applique l"algorithme d"élimination des états en éliminant successivementq2,q1etq0:iq

0fq 1q 2ab "ab a b" iq 0fq 1a b"ab ab iq

0fb+ababa""if(b+ababa)L est donc dénoté par (b+ababa).

Exercice 12L"automate suivant reconnait le langage L :q 0q 1q 2q 3a ab ab a

On le rend complet en ajoutant un état puit :

q 0q 1q 2q 3q 4a bab ab a ba;b En inversant les états acceptants on obtient un automate qui reconnaitL :

Corrigé des exercices4.9q

0q 1q 2q 3q 4a bab ab a ba;b Exercice 13SiL1etL2sont deux langages reconnus par des automatesA1etA2nous savons calculer les

automates reconnaissant l"intersection et le complémentaire donc des automates reconnaissantL1nL2etL2nL1.

Il reste à utiliser l"équivalence : L1= L2()(L1nL2=;et L2nL1=;) pour conclure.

Exercice 14

Considérons un automate fini déterministeA= (;Q;q0;F;)qui reconnaitL, notonsAc(respec-

tivementCo) l"ensemble des états accessibles (respectivement co-accessibles) et considérons les trois automates :

Ap= (;Q;q0;Co;);As= (;Q;Ac;F;);Af= (;Q;Ac;Co;)

(les deux derniers sont non déterministes). AlorsApreconnaitpref(L),Afreconnaitsuff(L),Afreconnaitfact(L)(on peut aussi observer quefact(L) = pref(suff(L)).

Exercice 15

SoitA= (;Q;q0;F;)un automate qui reconnaitL. Pour toutq2Qon noteIql"ensemble des

mots qui étiquètent un chemin deq0àqetFql"ensemble des mots qui étiquètent un chemin deqà l"un des états

finaux deF. Ces deux langages sont respectivement reconnus par(;Q;q0;fqg;)et(;Q;q;F;)donc rationnels.

L"égalitépL=

q2QI q\Fqprouve alors quepL est aussi rationnel.

Exercice 16

SoitA= (;Q;q0;F;)un automate qui reconnait le langageL. On noteIl"ensemble des états

accessibles à partir deq0en suivant un chemin étiqueté par un mot deK. On considère alors l"automate (non

déterministe) A0= (;Q;I;F;); nous allons montrer que A0reconnait K1L. Considérons un motv2K1Letu2Ktel queuv2L. Puisqueuv2Lle cheminq0uv qfmène à un état

acceptantqf2F. Ce dernier se décompose en deux cheminsq0u qv qfavecq2Ice qui montre quevétiquète

un chemin menant d"un étatq2I à un étatqf2F.vest donc reconnu par A0.

Réciproquement, sivest reconnu parA0il existeq2I,qf2Fet un cheminqv qfétiqueté parv. Par définition

deIil existeu2Ket un cheminq0u qétiqueté paruce qui prouve queuvest reconnu parA, donc queuv2L.

Lemme de l"étoile

Exercice 17

Supposons le lemme de l"étoile vérifié par le langageL1et posonsu=",v=aketw=bk+1. Le motuvwappartient àL1doncvse factorise env=ak1ak2ak3aveck2>1et pour toutn2N,uv1vn+12v3w= ak+nk2bk+12L1, ce qui est absurde.

Supposons le lemme de l"étoile vérifié pour le langageL2et posonsu=ak,v=bk,w=". Alors il existek2>1tel

que pour toutn2N,akbk+nk22L2, ce qui est absurde.

Supposons le lemme de l"étoile vérifié pour le langageL3et considérons un entier premierptel quep>k. Alors

apse factorise sous la formeak1ak2ak3aveck2>1et pour toutn2N,ap+nk22L3. En particulier, pourn=ple nombrep+pk2doit être premier, ce qui est absurde.

Exercice 18

Si le langage deDickétait rationnel il existerait un automate reconnaissant les mots de la forme

anbn; or nous avons vu que dans ce cas il existek2>1tel que le motanbn+k2soit reconnu, et ce dernier mot

n"est pas un mot deDick. http://info-llg.fr

4.10option informatiquePour toutk2Nle mot(1+(1+(1+(...1))...)(comportantkparenthèses ouvrantes et fermantes) appartient

au langageCaml; en posantu=(1+(1+(1+(...1,v=))...)etw="le second lemme de l"étoile conduit à une absurdité.

Exercice 19

SupposonsLrationnel; d"après le second lemme de l"étoile il existe un entierktel que pour tout palindromem=uvwtel quejvj>kse factorise sous la formem=uv1v2v3wavecjv2j>1,jv1v2j6ket8n2N, uv1vn2v3west un palindrome. En considérant le motm=akbakavecu=",v=aketw=bakon prouve l"existence d"un entierp >0 tel que pour toutn2N,ak+npbakdoive être un palindrome, ce qui est absurde.

Exercice 20

SupposonsLrationnel et notonskl"entier qui intervient dans la première version du lemme

de l"étoile. Si la conjecture est vraie il existep>ktel que2p1soit un nombre premier et dans ce cas le mot

1pappartient àL. D"après le lemme de l"étoile ce mot se factorise sous la formeuvwavecjvj>1et pour tout

n2N,uvnw2L. En posantv= 1jon prouve que pour toutn2Nle mot1p+njappartient àL, autrement dit que

2p+nj1est premier. Mais en prenantn=pon aboutit à une absurdité car2p(j+1)1est divisible par2j+11>3.

quotesdbs_dbs47.pdfusesText_47

[PDF] Corrigé des exercices 3. Le langage des mots

Chapitre 4option informatique

Corrigé des exercices

Automates finis déterministes

Exercice 1

1aba;b

Le lang agedes mots admettan tabapour facteur :q

Le lang agedes mots admettan tabapour sous-mot :q

Exercice 2Posonsn= 2p+ravecr2 f0;1g; alors :

D"où l"automate :

4.2option informatiqueq

1Pour lire les entiers à partir du bit de poids le plus faible, il suffit de considérer l"automate transposé, c"est-à-dire

Exercice 3

Exercice 4

D"où l"automate :

Corrigé des exercices4.3q

00;12.Les mots de E son treconn uspar l" automate:

3.NotonsL1le langage dénoté par01etL2le langage dénoté par(10). AlorsS=EL1L2doncSest reconnu

4.4option informatiqueletcoaccessible a =

Corrigé des exercices4.5

On désigne par la lettre :

013010230212030a;b

Exercice 8T

On obtient pour A

0l"automate :

4.6option informatiqueq

00l"automate :q

Exercice 9L"automate non déterministe :q

Corrigé des exercices4.7

Théorème deKleene

7acaac

4.8option informatiqueq

0fb+ababa""if(b+ababa)L est donc dénoté par (b+ababa).

On le rend complet en ajoutant un état puit :

Corrigé des exercices4.9q

Exercice 14

Ap= (;Q;q0;Co;);As= (;Q;Ac;F;);Af= (;Q;Ac;Co;)

Exercice 15

L"égalitépL=

Exercice 16

Lemme de l"étoile

Exercice 17

Exercice 18

4.10option informatiquePour toutk2Nle mot(1+(1+(1+(...1))...)(comportantkparenthèses ouvrantes et fermantes) appartient

Exercice 19

Exercice 20

1pappartient àL. D"après le lemme de l"étoile ce mot se factorise sous la formeuvwavecjvj>1et pour tout

2p+nj1est premier. Mais en prenantn=pon aboutit à une absurdité car2p(j+1)1est divisible par2j+11>3.