Théorie des langages : Td 2 automate finis
Télécharger PDF1 UNIVERSITE DE CONSTANTINE 2 Faculté des NTIC Module : TL / Licence 2
ème année
Année 2017/2018
TD n°2
Exercice 1Soit V
T ={a,b,c,d}. Donner une grammaire G qui génère L={cc*bd, a(ba)*bcc*ab}. G=(VT ,V
N , S,R) V
N ={S, C,B} R={ ScCbd/aBbcCab;CcC/; BbaB/}
Exercice 2Soit V
T ={a1 , a2 , ..., an }. Donner une grammaire G qui engendre le langage VT *. G=(VT ,V
N , S,R); V
N ={S,A} R={ S AS/;
A a1 / a2 / ..../ an }
Exercice 3Donner une grammaire qui engendre chacun des langages suivants : a) L
1 = { w {a, b, c}* / w contient au moins une occurrence de la lettre ‘a’ } ; b) L
2 = { w {a, b}* / w = an bm a ou w = ba
n ; n, m ≥ 1 } ; c) L
3 = { w {0, 1}* / w = 1(101)n 00 ou w = 0(010)n 11, n ≥ 0 } ; d) L
4 ={w є {0,1}* /w a un nombre de 1 égal au nombre de 0}. e) L5 ={w є {0,1}* / w ne contient pas de 0 consécutifs }. f) L
6 ={w є {0,1}* / w ne contient ni 1 consécutifs ni 0 consécutifs}. a) Soit G1=(VT ,V
N , S,R)V T
={a,b,c} ;V
N ={S,A} R={S AaA ; A aA/bA/cA/} b) Soit G2=(VT ,V
N , S,R)V T
={a,b} ;V
N ={S,A,B} R={S ABa/bA ; A aA/a; BBb/b} c) Soit G3=(VT ,V
N , S,R)V T
={0,1} ;V
N ={S,A,B} R={S 1A/0B ; A 101A/00; B010B/11} d) Soit G4=(VT ,V
N , S,R)V T
={0,1} ;V
N ={S} R={S S0S1S/S1S0S/} e) Soit G5=(VT ,V
N , S,R)V T
={0,1} ;V
N ={S} R={S 1S/0A/; A1S/} f) Soit G6=(VT ,V
N , S,R)V T
={0,1} ;V
N ={S,A,B} R={S 1A/0B/; A0B/;B1A/} 2
Exercice 4Soit le langage L défini sur V={a,b,c} comme suit : L = { a2n bc
2 m + 1 / n, m ≥ 0 } a)Trouver une grammaire de type 2 qui engendre L b)Montrer que L est de type 3 a) Soit G=(VT ,V
N , S,R)V T
={a,b,c} ;V
N ={S,A,B} R={S AbB/bc; AaaA/;BccB/c} b) Soit une grammaire de type 3 G1=(VT ,V
N , S,R) ;VT ={a,b,c} ;V
N ={S,A,C,D} R={ S aA/bC;AaS; CcD/c;
DcC ;}
Exercice 5Soit le langage L = ensemble de tous les mots de {0, 1}* qui contiennent un nombre pair de « 1 ». a)Trouver une grammaire de type 2 qui engendre L b)Montrer que L est de type 3 a)G = ({0, 1}, {S}, S, R) où R : S → 0S / S1S1S | b)L peut être généré par une grammaire, de type 3, G’ = ({0, 1}, {S, A}, S, R’) où R’ : S → 0S / 1A / A → 0A / 1S
Exercice 6Soit la grammaire G =(VT ,V
N , S,R)V T
={a,b,c} ;V
N ={S,B,H,D} R :{S → cBc ; B → baH/bD ; D → bDa/ba; H → baB} Quel est le langage engendré par G? L(G)={ w {a, b,c}* /w=c(ba)2n bm+1 am c, n 0 et m 1}
Exercice 7Soit la grammaire G=(VT ,V
N , S,R)V T
={a,b} ;V
N ={S} R:{S → aSa / bSb /a/b} a)Quel est le type de G ? b) Déterminer le langage L engendré par G. c) Quel est son type ? a)G est de type 2 b)L={w {a, b}* / w est un palindrome de taille impaire} c) L est de type 2 car il y a une relation de puissance (puissances liées) entre les symboles des mots du langage 3
Exercice 8Soit la grammaire G =(VT ,V
N , S,R)V T
={a,b} ;V
N ={S,A,B} R :{ S → AB | ε
A → aAb | ε
bB → Bbb
bB → b } a)Quel est le type de G ? b)Déterminer le langage L engendré par G. c) Quel est son type ? a)G est de type 1 car toutes les règles sont de type 1 b)L(G)={ w {a, b}* / w =an b
m / n 0 n<=m<=2n} c) L est de type 2 car on peut trouver une grammaire de type 2 équivalente à G G’ = ({a, b}, {S,B}, S, R’) où R’ : S → aSbB | →b
Exercice 91) Soit le langage L ={a
n bm / n ≠ m , n et m ε N} a) Donner, en justifiant, une grammaire G engendrant L.
b) Donner, en justifiant, le type de L 1) G =(VT ,V
N , S,R)V T
={a,b} avec VN = {S,A,B,D} R = { S → AB/BD; AaA/a BaBb / ε
D → bD/b}. 2) Donner une grammaire de type 2 qui génère L. L={an bn c
m / n,m ≥0 }U{ an bm c
n / n,m ≥0 } U { an bm c
m / n,m ≥0 } 2) G =(VT ,V
N , S,R)V T
={a,b} avec VN = {S,A,B,C,D,E} R = { S → AB/C/E; AaAb/ ε BcB / ε
C→ aCc/D
DbD/ ε
EaE/F FbFc/ ε
}.
Exercice 10Soit la grammaire G =(VT ,V
N , S,R)V T
={a,b} avec VN = {S} R = { S → aSa; S → bSb; S → ε}. a) Montrez que aabbaa ∈ L(G) b) Quel est le langage L engendré par G ?
a) Par dérivation : SaSaaaSaaaabSbaaaabbaa b) L={ w =w1 w~ 1w 1
{a, b}* } 4
Exercice 11Soit G=({a,b,d}, {S, B, C}, S, R). R=
S aSBC bB b2 S aBC bC bd
CB BC dC d2 aB ab Quel est le langage L engendré par G ?
L={ ={an bn dn / n 1 }
il est de type 1
Exercice 12Soit la grammaire G = ( V
T , V
N , S , R) avec : V
T = { a, b } ; V
N = { S } R
= { S →aSa, S→ aS / bS / a / b } a ) Quel est le type de G ?
b ) Quel est le langage L engendré par G ?
c ) Quel est le type de L ? a) G est de type 2 b) L(G)= {a, b}+ c) L est de type 3 car on peut trouver une grammaire de type 3 équivalente à G
G’ = ({a, b}, {S}, S, R’) où R’ : S→ aS / bS / a / b