EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

EXERCICES du THÈME 2 : Langages Réguliers

À propos des AFD (automates finis déterministes) :

1. Raisonnez sur la véracité ou la fausse des affirmations suivantes, en vous appuyant sur la
théorie vue en classe. Si M = (Q,Σ,δ, q0, F) est un automate fini déterministe
totalement spécifié par F = Q, alors L(M) = Σ.

2. Mer M = (Q,Σ,δ, q0, F) un AFD avec Q = {q0,q1,q2},Σ= {a,b}, F = {q2} et la fonction

de transition

δ a b
q0 q0 q1

q1 q2 q1

q2 q2 q0

a) Dessine l'automate M
b) Tracez les calculs de M qui traitent les mots abaa, bbbabb, bababa
bbbaa
c) Quelles mots des traités en (b) sont acceptés par M ?

3. Busca tres palabras aceptadas y tres palabras rechazadas por cada uno de los
suiivants automates montrant le calcul qui les traite. Détermine lesquels
d'eux sont totalement spécifiés. Saurais-tu quel est le langage accepté
pour chacun d'eux ?
a) a b) a
b
a b
b a
a,b

b
a
b
a,b
a,b

page 1
EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

c) a b a,b

b un

d) b un e) b a

un b a b
b un b un

a a,b

f) g) b a
a b un

a a b b
b un a b un
b

b un
a

4. Construisez des AFD qui acceptent chacun des langages définis.

sur l'alphabet Σ= {a,b} :
a ) L = {xΣ* : la longueur des x est divisible par 3}
b ) L = {xΣ*:abano est une sous-mot de x}
c ) L = {xΣ* : x commence par ay et termine par ab}
d ) L = {xΣ* : xtient un nombre pair de a's et un nombre pair de b's }
e ) L = {xΣ* : x a trois a's consécutifs}
f ) L = {xΣ* : toute apparition de la sous-mot aba dans x, est soit suivie de
bb, o est à la fin du mot }
g ) L = {xΣ* : six commence par un et contient le sous mot aay six commence
porbcontiene la subpalabraaa
h ) L = {xΣ* :x a un nombre pair d'apparitions de la chaîne ab}
i ) L = {xΣ* : abes sous-mot dexsi et seulement sibaes sous-mot dex}
j ) L = {xΣ* :x est formé par la concaténation d'un nombre arbitraire
R |y|=2 }
de chaînes de la formayy, avec
k ) L = {xΣ* : x ne contient aucun préfixe dans lequel la différence entre le
le nombre d'a's et de b's doit être supérieur à trois (en faveur de l'un ou de l'autre)

page 2
EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

5. (Exercice spécial) Construisez un AFD qui accepte le langage suivant :

L = {x{a,b}* : x ne contient pas le sous-mot bab et se termine par aba}

6. (Exercice spécial) Montre que la notion de langage acceptée par un AFD

ne dépend pas de l'alphabet particulier de celui-ci (tant qu'il contient au moins les
symboles impliqués). C'est-à-dire, prouve que :

SiΣ* L y∏ Σ, alors il existe un AFD sur l'alphabet Σ qui accepte

L si et seulement si, il existe un autre AFD sur l'alphabet ∏ qui accepte L.

Sur les AFND (automates finis non déterministes) :

7. Busca tres palabras aceptadas y tres palabras rechazadas por cada uno de los
les automates non déterministes suivants, montrant tous les calculs qu'ils
procèdent. Saurais-tu quel langage accepte chacun d'eux ?
a) b b
a un

b b
b) b b c) un
a
b

un a b
a un
b

8. Construisez des AFND qui acceptent les langages suivants sur l'alphabet
Σ= {a,b,c}

a) L = {xΣ* : x contient un certain nombre de a's séparés par une chaîne de symboles}
de longueur 4*i, avec i≥0 }
b)L = {xΣ* : |x|≥5 et le cinquième symbole compté depuis la fin est a}
c)L = {xΣ* : niaanibbson sous-chaînes dex}
d)L = {xΣ* :xtien a bya b a como subcadena }
e) L = {xΣ* :ccces sufijo dexy en ninguna otra posición dexpueden
trouver deux symboles identiques consécutifs }

p. 3
EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

f ) L = {xΣ* : x a trois symboles identiques consécutifs}

g ) L = {xΣ* : les symboles de position multiple de trois sont c's }

9. (Exercice spécial) Construisez un AFND qui accepte le langage suivant L =

{x{a,b,c}* :xcommence et se termine paray entre chaque apparition deay la
suivant, il y a un nombre pair deb's ou un nombre impair c's }

10.(Exercice spécial) Combien d'automates finis déterministes et avec deux états

Peuvent-ils être construits sur l'alphabet {0,1} ? Acceptent-ils tous des langages
différents ? Et parmi eux, combien sont totalement spécifiés ? Et si nous construisons
automates finis non déterministes ?

[Link] le langage régulier L = { x {a,b}*:

a |x| mod2b = 1 |x|mod3 = 0 aba
est sous-mot de x }. Suivez les étapes indiquées ci-dessous sans
construire à aucun moment l'automate fini indiqué :

a) Supposons que vous souhaitiez construire un automate fini M qui reconnaisse L.

Indique combien d'états M aurait et expliquez pourquoi. Enumérez ces états.
états, expliquant à quoi chacun d'eux sert dans ta construction.
Indiquez quel serait l'état initial et quels seraient les états finaux.
b) Choisis trois états au hasard et indique quelles seraient leurs transitions et à
quels états nous mèneraient.
c) Reconstruisez les calculs associés aux mots aababbybabab.

Sur les GR (grammaires régulières) et les GL (grammaires linéaires) :

[Link] des grammaires régulières ou linéaires à droite qui génèrent chacune d'elles.
les langages suivants sur l'alphabet terminal Σ= {a,b,c}

a) {xΣ* : |x|amod 2 = 0 }
b){xΣ* :xcommence par a et contient le sous-mot bbb}
c){xΣ* :x ne contient pas trois b's consécutifs }
d){xΣ* : |x| un+ |x|bmod 3 = 0 }
e) {xΣ* :xcontient les sous-mots aa, bb et cc}
f) {xΣ* : x ne contient pas les sous-mots abaniaca}
g){xΣ* : chaque apparition de aenxes précédée de b et suivie de c}
h){xΣ* :xne contient aucune apparition de la sous-chaîne a après la
dernière apparition du symbole
i) {xΣ* :x contient deux d’une séparation par un nombre impair de symboles}

p. 4
EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

j) {xΣ* :x contient la sous-mot ab mais ne contient pas la sous-mot aba}

Parmi elles, dis lesquelles sont régulières et lesquelles sont linéaires. Transforme les
linéaires en réguliers.

13. (Exercice spécial) Soit G=(N,Σ, P, S) une grammaire linéaire à droite, avec
{S,A,B}ε,aaA,abaS,
bbab,aSba, Baaab,abAS,abBAbSb.

a ) Lesquelles d'entre elles pourraient être des formes sentencielles de G ?

b ) Décrivez la structure générale d'une forme propositionnelle de G.
c ) Démontre par induction que les formes propositions de G ne peuvent pas être
différentes de ce qui a été décrit dans la section précédente.

14.(Exercice spécial) Une grammaire quasi-régulière à droite est définie comme

une grammaire G = (N,Σ, P, S), où les règles de P répondent à l'une des
3 formes suivantes : A → ε, A →aB, A →a, avec A,B N,aΣ. Considérez le
algorithme suivant :

G = (N, Σ, P, S) grammaire quasi-régulière à droite

INCOGNITA
Procédure : Construire INCOGNITA = ( N1,Σ,δ, S, F) où
N1= N {Z}
F = {Z} A→ ε P
Bδ(A,a) A→aB P
Zδ(A,a) A→aP

a) Appliquez l'algorithme à la grammaire suivante : G = ({S,A,B}, {a,b,c}, P, S) étant P

l'ensemble des productions
S → aA | aB A→bA |b B→cB |c

b) À quel modèle appartient INCÓGNITA ? Justifiez votre réponse.

c) Justifie l'affirmation suivante : « Tout langage généré par une grammaire »

régulier (à droite) peut être généré par une grammaire quasi-régulière (à
droite) et vice versa.

p. 5
EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

Sur les ER (expressions régulières) :

15. Dites si les affirmations suivantes sont vraies ou fausses :

a ) baaL(a*b*a*b*) b ) L(b*a*)∩L(a*b*) = L(a*b*)

c ) L(a*b*)∩L(c*d*) = d ) abcdL((a(cd)*b)*)
e) Les expressions régulières α=εyβ=(ε )* son équivalents.

16. Pour les expressions régulières suivantes, écrivez tous les mots de longueur
moins ou égal à six appartenant au langage qui les génèrent, et décrit ce dernier
langue dans chaque cas :

a) (10)* (01)* b ) (10 01)*

c ) (11 0)*(00 1)* d ) (1 01 001)*( ε 0 00)
e ) [00 11(01 10)(00 11)*(01 10)]*

[Link] Σ ={a,b}. Écrivez des expressions régulières pour les langages suivants :
a) cadenas avec au moins trois a
b) chaînes avec au plus trois a's
c ) cadenas avec un numéro dea's divisible par 3
d ) chaînes avec au moins une apparition de la sous-chaîne aaa
e) cadenas dans lesquelles les lasses sont regroupées par groupes d'au moins trois.

[Link] Σ ={a,b}. Construisez une expression régulière pour le langage formé par les
cadenas qui ne contiennent pas la sous-chaîneaaa. Il faut d'abord faire l'AFD,
obtenir à partir de lui la GRD et, en résolvant les équations correspondantes,
arriver à l'expression régulière.

19.(Exercice spécial) Soit Σ ={a,b}. Construisez une expression régulière pour le

langage formé par les chaînes qui contiennent exactement une apparition de
la sous-chaîneaaa. Il faut d'abord faire l'AFD, obtenir à partir de celui-ci la GRD
y, en résolvant les équations correspondantes, parvenir à l'expression régulière.

p. 6
EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

20. Construisez des expressions régulières pour désigner les langages suivants :

a) {w{a,b}* : wacaba enab}

b ) {w{a,b}*: |w|a ≠1} .
c ) {w{a,b}* : wtiene un nombre pair de a's et termine par ab}
d ) {w{1,0}* : w ne contient pas 101 comme sous-mots }
e ) {w{1,0}* : wcommence par101 et se termine par101}
f ) {w{a,b,c}* : entre chaque dosa's dewhay un nombre dec's multiple de 3}

[Link] la définition inductive des expressions régulières, la règle qui affirme que
ε c'est une expression régulière qui peut être supprimée, car avec le reste des règles
Il est possible de construire une expression α telle que L(α) = {ε}. Pourquoi ?

Sur les ER équivalents aux automate :

22. Construisez des expressions régulières équivalentes aux AF suivants :

a b b a,b
un

b a
b
a b
a
b
a,b

Sur les ER équivalentes aux grammaires :

[Link] des expressions régulières équivalentes aux grammaires linéaires à la

droite dont les règles de production figurent ci-dessous :

a) S→aS |bS |abaA |ababaB |abababaC |abababa

A→aA |bA |abaB |ababaC |ababa
B→aB |bB |abaC |aba
C→aC |bC |a|b
b) S → a | aA | bB

A→b|bA
B→a|aA|aC
C→b|bA|aD
D→aC |bD

p. 7
EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

Exercices théoriques sur les ER :

24. (Exercice spécial) Supposons comme déjà démontré que pour n'importe quel
les expressions régulières α, 1..., α, β,n..., β1 se vérifient
n que :
i ) (α1α 2...αn)* = (α1*α2*...αn*)*
ii ) (α1α 2...αn) (β1β 2...βm) =α1β 1α 1β 2...α1β mα 2β 1
...αnβ 1...αnβ m

On dit qu'une expression régulière est en forme normale disjointe si elle a la

formaα1α 2...α, avec n≥1n et yα, ...,1 α nsont des expressions régulières dans les
que n'apparaît pas le symbole " ".

a ) Utilisant les résultats précédents i) yii) démontre que pour tout

expression régulière α existe un autre équivalentα ) en forme normale
dilemme.
b ) Écris la forme normale disjonctive des expressions suivantes
réguliers
(ε (0 1)*100)0*
((10*01*) (00*11*))

[Link] α une expression régulière quelconque :

a ) Concevez un algorithme récursif pour décider si α est équivalent à la
expression régulière .
b ) Décrivez un autre algorithme pour obtenir à partir de α une autre expression régulière

equivalentesinvac(α )que, ou bien ne contient pas la sous-expression , o es

exactement l'expression régulière (inévitable quand α est équivalent à
).
c ) Applique l'algorithme effectué dans la section (b) à l'expression régulière :
(1(11)*)*(0 0 01)*( (1 0)*10).

26. Une expression régulière qui ne contient aucune apparition de la

sous-expression

a ) Concevez un algorithme récursif pour décider si le mot vide appartient ou

non à L(α).
b ) Décrivez un autre algorithme pour obtenir à partir de α une autre expression régulière

équivalentesineps( ), quiα ne contient toujours pas d'apparitions de , et que

a la forme ,βóβ ε ε, où vous devez une expression régulière qui ne
contient des apparitions de ε (c'est-à-dire, ensineps( α )nous supprimons tous les
apparitions de ε sauvez-en une au cas où ce serait strictement nécessaire

p. 8
EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

pour maintenir l'équivalence).

c ) Appliquer l'algorithme trouvé dans(b) à l'expression régulière (((1 ε )*ε )
01)* ε 1 ε (01) ε ε) ε
(10* .
d) Supposons maintenant que, dans la définition d'une expression régulière, on supprime
y ε régulières. À la lumière
les clauses qui garantissent que ses expressions
des résultats de cet exercice et du précédent, quels seraient les
langages réguliers qui ne pourraient pas être désignés par ceux-ci ? Et si
nous enlevons seulement une des clauses ?

Sur les AFND et leur relation avec les ER :

Construis ε-AFND qui acceptent les langages suivants sur Σ {a,b, c}

a ) L = { xΣ* : les apparitions de a ne peuvent pas être suivies de c, les
les apparitions ne peuvent pas être suivies de a, et les apparitions disent
xne peuvent pas aller ensemble deb}
b) L = {xΣ* : x ne peut avoir aucune a occupant une position ultérieure}
à la de une byxno contient des isolées
c ) L = {xΣ* : x est formée par un ou plusieurs groupes de a's séparés par
chaînes de 1, 2 ou 3b's }
d) L = {xΣ* :x peut être décomposé comme une concaténation de trois
subpalabrasy,zywcumpliendo que enycada grupo dea's tiene
longueur paire, chaque groupe de deb's a une longueur paire et chaque groupe
dec's a une longueur paire }

[Link] des automates finis qui reconnaissent les langages désignés par les
expressions régulières suivantes :
a ) a*bb*(a b)ab* b ) b((aab*a4)b)*a
+ b*)+
c ) (a b*a + d ) (((b*a)*a)*a)*a
2 3 4 4
e ) (a)*(b)*(c)*(a)*(b)*(c)* 3 2

29.(Exercice spécial) a) Construis un automate, M, qui rejette tous les

mots de longueur impair ayant les deux derniers symboles identiques. Doit
accepter, par exemple, les motsabaa,a,abay rejeterabb,babbbaaaa.
Vous pouvez le construire directement (avec les explications appropriées) ou l'obtenir
del apartado suivant par un algorithme de transformation.

p. 9
EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

b) Concevez une expression régulière qui génère le même langage que dans la section
anterior . Vous pouvez la concevoir directement (avec les explications appropriées) u
l'obtenir de la section précédente par le biais d'un algorithme de transformation.

Sur les équivalences entre automates :

30. Construisez des AFD équivalents aux AFND suivants :

a) ({0, q1, q2, q3}, {0,1},δ1, q03} )

b ) ({ q0, q1, q2, q3}, {0,1},δ2, q01,q3} )
δ1 0 1 δ2 0 1
q0 q0,q1 q0 q0 q1,q3 q1
q1 q2 q2 q1 q2 q1,q2
q2 q3 - q2 q3 q0
q3 q3 q3 q3 - q0

31. Construisez les AFD équivalents des ε-AFND suivants :

un
a
un
b
ε b ε

un
ε
b ε ε
b un ε

un ε un
a
a ε a
a ε

un
b b

p. 10
EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

32. Étant donné les automate finis suivants, construisez l'automate fini minimal.
équivalent à chacun d'eux :
b

a a q2
q0 q1

b
b b a

q3 a un q5
q4

a, b
b

q0
1 0

q1 q2

1 0 1 0

1
q3 q4 q5 q6

1,0 0 1 1,0

33. Soit le langage L = {a100+3ibj: i, j≥0} défini sur l'alphabetΣ = {a‚b}.

a) Montre que L est régulier, en donnant une α querégulière
expression le
dénote.
b) Décrivez à quoi ressemblerait un AFD M, totalement α.
spécifié, équivalent à
Assure-toi que ce soit l'automate minimal. Prends un état quelconque de M, et
vérifiez qu'il n'est équivalent/indiscernable d'aucun des autres
états.
Remarque : Il n'est ni nécessaire ni souhaitable que vous appliquiez les algorithmes de
transformation ou minimisation. En fait, il n'est pas nécessaire que tu écrives le
automate M complet.

[Link] qu'on vous donne deux expressions régulières α et β, et qu'on vous demande de

vérifiez s'ils sont équivalents ou non. Expliquez le processus que vous suivriez pour
résoudre cela.

p. 11
EXERCICES de MAC 1 – ALF (Thème 2) Cours 2010/2011

[Link] si les affirmations suivantes sont vraies ou fausses, en justifiant votre réponse.
forme brève mais convaincante.

a) Nous avons un AFD sur l'alphabet {a,b} qui contient deux états non
finales, p et q, avec les transitions suivantes :
a b
p p q
q p q
Sans connaître le reste de l'automate, nous pouvons affirmer que ces états sont
nécessairement indistinguables.
b) Si M =Σ, δ(Q,
, q0, F) est l'automate minimum équivalent à l'AFD, N = (P,
Σ, γ, p0, G), le cardinal de F et G doit être le même.

36.Démontre qu'ils ne sont pas réguliers sur l'alphabet Σ= {a,b} :

a ) {wwΣ: * w c'est le mot qui résulte du changement de chaque apparition enwdea

porby viceversa
b ) {wΣ:w=w*R|w|un= |w|b}
c ) {anbm: m≤n≤2*m }
d ) {ajebjak: j = max(i,k) }
e ) ajebjak: i, j, k > 0 (i ≤ j j ≥ k i = k) }
f ) Invalid [Link]: i, j, k >0 (i = j i = k j = k) }
g ) {wΣ:wtiene* au moins un préfixe avec plus de b's que a's }

[Link]ère l'alphabet {M,D,C,L,X,V,I} et le langage des nombres

romains. Montrez que c'est un langage régulier en construisant un automate
fini avec des transitions vides qui le reconnaissent. N'oublie pas que, par exemple, VIII
ce n'est pas un nombre romain, et nous devons écrire IX à la place. Peut
il est utile de construire l'expression régulière puis lε-AFND
correspondant.

p. 12