[PDF] Automates et langages - IRIF PDF corrige.pdf

Corrigé de l'examen — RICM1— 8 janvier 2003 Exercice 1 : Un automate et son langage 1 Voici les productions de grammaire obtenues directement `a partir

Langage C : énoncé et corrigé des exercices Exercice 10 Ecrire un progra mm e se co m portant co mm e une ca l cu l atrice , c 'est- à -dire exécutant l a b ouc l

[PDF] CORRIGE DE LEXERCICES EN VUE DE LA - UFR EILA

En quoi consiste la fonction conative du langage et à quel facteur de la communication, selon Romain Jakobson, se rattache-t-elle ? Illustrez votre réponse par un

[PDF] Langage C : énoncé et corrigé des exercices - Talib24

Langage C : énoncé et corrigé des exercices 1 FIG 1 - Figure de l'exercice 25 I* Fonction qui retourne le nombre de caractères de la chaîne*/ int strlen (char

[PDF] Corrigé des exercices

option informatique Corrigé des exercices • Automates finis déterministes £ ¢ ¡ Exercice 1 1 Le langage des mots contenant au moins une fois la lettre a : q0

[PDF] Langages formels Corrigé – Laboratoire 1 Exercice 1 a) ER : (a+b

d) ER: a*ba*ba* e) Lorsqu'il faut construire un automate pour un langage L qui est décrit comme l'union, l'intersection ou la différence de deux autres langages

[PDF] EXERCICE- REGISTRES DE LANGUE- LE - Le Baobab Bleu

LE LANGAGE STANDARD, FAMILIER ET L'ARGOT 01 Indiquez CORRIGÉ 1 a langage familier: un pif • un toubib • un gosse/un môme • un copain •un pote

[PDF] Automates et langages - IRIF

Corrigé de l'examen — RICM1— 8 janvier 2003 Exercice 1 : Un automate et son langage 1 Voici les productions de grammaire obtenues directement `a partir

[PDF] Expressions et idiotismes exercices et corrigé

Exercices 1 Complétez ces expressions en vous servant de la banque de mots nez pouces doigts ventre poil souffle cheveu esprit gueule pieds langue yeux

[PDF] Exercice 1 : - UV

Exercices Corrigés Initiation aux Base de données • Algèbre relationnelle Corrigé de l'EXAMEN Ecrire en langage algébrique les requêtes suivantes : 1

[PDF] CORRIGE

Un acte illocutoire est un acte qui consiste à signaler un acte de langage ❑ L' acte illocutoire est le fait de dire quelque chose 13 Qu'est-ce que le principe d'

[PDF] cours langage c++ pour débutants pdf

[PDF] cours langage c pdf pour debutant

[PDF] tp corrigé langage c

[PDF] langage c++ cours pdf

[PDF] apprendre le latin livre

[PDF] apprendre latin autodidacte

[PDF] aprender latin pdf

[PDF] cours de francais pour etranger bordeaux gratuit

[PDF] cours de francais pour etranger metz

[PDF] cours de français gratuit vaud

[PDF] alliance francaise bordeaux aquitaine

[PDF] cours de français pour étrangers metz

[PDF] cours de français lausanne pas cher

[PDF] association cours de français bordeaux

[PDF] cours de français gratuit lausanne

Automates et langages

Corrig´e de l"examen - RICM1- 8 janvier 2003

Exercice 1: Un automate et son langage

1. Voici les productions de grammaire obtenues directement `a partir de l"automate:

P→aP P→aQ

Q→bP Q→R

R→bR R→cQ R→bP R→?

Les non-terminaux de la grammaire sont{P,Q,R}, le symbole initial estP.

2. En d´enotant avecXp,Xq,Xrles langages accept´es `a partir des ´etatsp,qetrrespectivement,

le syst`eme d"´equations pour ces langages est: ?X p=aXp+aXq X q=bXp+Xr X r=bXr+cXq+bXp+? En rempla¸cantXqdans les ´equations 1 et 3 on obtient: ?Xp=aXp+abXp+aXr X r=bXr+cbXp+cXr+bXp+?

La deuxi`eme ´equation implique:

X r= (b+c)?(cbXp+bXp+?) d"o`u, en rempla¸cant dans la premi`ere ´equation: X p= (a+ab)Xp+a(b+c)?(cb+b)Xp+a(b+c)? Finalement, on obtient l"expression r´eguli`ere ´equivalente `a l"automate: X p= (a+ab+a(b+c)?(cb+b))?a(b+c)?

3. Le tableau de successeurs obtenu par d´eterminisation est:

A B C D

{p} {p,q,r} {p,r} {q,r} a{p,q,r} {p,q,r} {p,q,r} ∅ b ∅ {p,r} {p,r} {p,r} c ∅ {q,r} {q,r} {q,r}

L"automate est donc:

A BC D b,c ab c a c b a ab ca,b,c Exercice 2: Un langage r´egulier plus int´eressant

1. Le langage contient les mots de longueur multiple de 3 et impaire, form´es avecle symbolea.

2. SoitK= (aaa)?etL= (aa)?. L"automate acceptantKest:

1 2 3 aa a

L"automate acceptantLest:

pq a a

L"automate acceptant

Lest: pq a a

L"automate acceptantM=K-L=K∩Lest:

1,p2,q3,p

1,q2,p3,q

aa a aa a

3.Mn"est pas vide, car l"automate contient un chemin 1p→2q→3p→1qde l"´etat initial `a

l"´etat final. Mcontient une infinit´e de mots, car l"automate contient un cycleσ= 1p→2q→3p→

1q→2p→3q→1paccessible de l"´etat initial, tel que l"´etat final est accessible `a partir de

σ, ´etiquet´e par un mot non videa6.

4.a3(a6)?

5. 3 + 6k|k?N

Exercice 3: Un langage non-r´egulier

1. La grammaire qui engendre{aibj|i < j}peut ˆetre donn´ee avec les productions suivantes:

I→aIb|Ib|b

La grammaire qui engendre{aibj|i > j}peut ˆetre donn´ee avec les productions suivantes:

J→aJb|aJ|a

La grammaire qui engendre T est donn´ee par les productions ant´erieures, plus les productions suivantes:

S→I|J

Les non-terminaux de la grammaire sont{S,I,J}. Le symbole initial estS.

2. Voici un automate `a pile pourT, en supposant que l"automate commence avec une pile

contenant le symboleZ(l"´etat A sert a accepter les mots qui ont plus dea, l"´etat B ceux avec plus deb.) A B a,push(a) b,pop(a) ?,pop(a) b,pop(Z) b

3.a?b?={anbm|n,m?N}

a ?b?-T={anbm|n,m?N? ¬(n?=m)}={aibi|i?N}

4. Supposons queTest r´egulier. Alors, par les propri´et´es de fermeture des langages r´eguliers,

Test aussi r´egulier. Commea?b?est r´egulier, il en r´esulte quea?b?∩T=a?b?-Test aussi r´egulier. Maisa?b?-T={aibi|i?N}n"est pas r´egulier (vu en cours). Par cons´equent, on a une contradiction de l"hypoth`ese de r´egularit´e deT.

Exercice 4: Une intersection

1. On a vu ces langages en TD.

P={anbmambn|n,m?N}

Q= ((a+b)3)?={w|w? {a,b}?et|w|est multiple de 3}

2. Nous allons utiliser comme non-terminaux pour l"intersectionS0,S1,S2,R0,R1,R2. La signifi-

cation du symboleSi(resp.Ri) est la mˆeme que celle deS(resp.R), et encore que le nombre de terminaux (c-`a-daetb) d´ej`a g´en´er´es esti(mod3). Chaque transition de la grammaire de d´epart donne plusieurs transitions de la nouvelle grammaire, ainsi pourS→aSbon obtient trois r`egles:S0→aS2b;S1→aS0b;S2→aS1b (si avant la production on avaiti(mod3) terminaux, alors apr`es on a 2 terminaux de plus, c-`a-di+ 2(mod3)). On peut terminer la d´erivation si est seulement si notre symbole est R, et le nombre de terminaux est multiple de 3, ce qui correspond `aR0dans la nouvelle grammaire. Pour cette raison la seule production qui donne?estR0→?.

[PDF] [PDF] Automates et langages - IRIF