Scribd
Importer
78 vues1 page

Exercices sur la théorie des langages

Le document présente trois exercices sur la théorie des langages. L'exercice 1 demande de déterminer si des mots appartiennent à des langages réguliers donnés. L'exercice 2 demande de donner une définition formelle pour sept langages. L'exercice 3 demande de calculer L2, L* et L+ pour trois langages.

Transféré par

informatiquehageryahoo.fr
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
78 vues1 page

Exercices sur la théorie des langages

Le document présente trois exercices sur la théorie des langages. L'exercice 1 demande de déterminer si des mots appartiennent à des langages réguliers donnés. L'exercice 2 demande de donner une définition formelle pour sept langages. L'exercice 3 demande de calculer L2, L* et L+ pour trois langages.

Transféré par

informatiquehageryahoo.fr
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Année universitaire : 2022/2023 2ème année LBC

Module : Théorie des langages

SÉRIE D’EXERCICES no1 Les Langages


Exercice 1
Pour chaque alphabet X et pour chaque langage L suivant, dites si les mots w1, w2, w3 et w4
appartiennent à L ou non.

X W1 W2 W3 W4 L
{a,b} aa ababb abb bbab {w ϵ X*/w=anbm ;n,m≥0}
{a,b,c} aabca aabb acbac ababc {w ϵ X*/w=(ab)ncm ;n,m≥0}
{a,b,c} aabaabcc abaabc bbcc aabaab {w ϵ X*/w=(anb)mcn ;n,m≥0}
{a,b} aababb aabb abaab baab {w ϵ X*/d(w)=0 ;et pour tout w’
préfixe de w, d(w’)≥0}
Remarque :

• La différence entre le nombre d’occurrences de a et le nombre d’occurrences de b dans w est


notée par : d(w)=|w|a-|w|b.
• Soit X un alphabet et soient x et y deux mots de X*.
✓ X est dit facteur gauche de y ou préfixe de y, s’il existe h ϵ X*, tel que y=xh.
✓ X est dit facteur droit de y ou suffixe de y, s’il existe h ϵ X*, tel que y=hx.
✓ X est dit facteur gauche propre de y ou préfixe propre de y, s’il existe h ϵ X+, tel que
y=xh.
✓ X est dit facteur droit propre de y ou suffixe propre de y, s’il existe h ϵ X+, tel que y=hx.

Exercice 2
Donner une définition formelle pour chacun des langages suivants :

1. L1={ ε,xxyy,xxxyyy,…}.
2. L2={ xxyyy,xxxxyyyyy,xxxxxxyyyyyyy…}.
3. L3={ y,x,xyx,yxy,xyyx,yxxy,xyyyx,…}.
4. L4={ xy,yx,xxyy,xyxy,xyyx,yyxx,yxyx}.
5. L5={ xyy,xxyyyy,xxxyyyyyy,…}.
6. L6={xy,xyxy,xyxyxy,…}.
7. L7={1000,1100,1001,0011,0110,0001}.

Exercice 3
Calculer L2 et L* et L+ dans chacun des cas suivants :

1. L={w ϵ {x,y}*/w=xnyn ;n≥2}


2. L={w ϵ {x,y}*/|w|x=|w|y }
3. L={w ϵ {x,y}*/w=(xy)*}

Vous aimerez peut-être aussi