Scribd
Importer
265 vues2 pages

Théorie des langages : Exercices TD1

Cet exercice contient 4 exercices sur la théorie des langages formels. Les exercices portent sur des opérations sur des chaînes de caractères, la reconnaissance de mots par des grammaires formelles, et la proposition de grammaires générant certains langages.

Transféré par

Doucson Seydou Fily Mallé
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
265 vues2 pages

Théorie des langages : Exercices TD1

Cet exercice contient 4 exercices sur la théorie des langages formels. Les exercices portent sur des opérations sur des chaînes de caractères, la reconnaissance de mots par des grammaires formelles, et la proposition de grammaires générant certains langages.

Transféré par

Doucson Seydou Fily Mallé
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

EPI SUP

Théorie des langages


Digital School
2022/2023
Préparatoire 2

TD1 : Série d’exercice n°1

Exercice 1:
Soit le mot x = ((acbc)𝑅 . (baca))𝑅 (α𝑅 désigne le reflet miroir de α).
1- Donner la chaîne de caractères à laquelle x est égal.
x = acabacbc
2- Quelle est la valeur de |x|, |x|a , |x|b , |x|c ?
|x| = 8; |x|a = 3 ; |x|b = 2 ; |x|c =3
3- Donner un préfixe propre de x contenant au moins deux lettres ‘c’.
X= acabacbc => X1= a; X2=ac; X3=aca; X4=acab; X5=acaba; X6=acabac => donc le prefixe de X
contenant au moins deux lettres ‘c’ est acabac
4- Donner un suffixe propre de x contenant une seule lettre ‘a’.
X= acabacbc => X1= c; X2=bc; X3=cbc; X4=acbc => donc le suffixe propre de x contenant une
seule lettre ‘a’ est acbc

Exercice 2:
Soit la grammaire G = ({a, b, c}, {S, A}, P, S) où P contient les règles suivantes :

S → aS | bA
A → cA | ε

1- Déterminer si les mots w1 = abac, w2 = aabccc, w3 = cabbac et w4 = ab sont dans L(G).


Les mot w1 et w3 n’appartiennent pas L(G).
les mots w2 et w4 sont dans L(G) : w2 : S→ aS→ aaS→ aabA→ aabcA → aabccA→ aabcccA →
aabccc et pour w4 : S →aS →abA→ ab = w4.
2- Trouver le langage généré par G (qu’on note L(G)).
L ={𝑎𝑛 b 𝑐 𝑚 pour n, m ≥ 0}

Exercice 3:
Considérons la grammaire G1 définie comme suit :

𝐺1 = ({a, +, =}{A, B, C},A,{


A → aAa | aBa,
B → +C ,
C → aCa | a=a })
1- Montrer si les mots suivants peuvent être générés ou pas par G1 :
w1 : a+a=aa,
w2 : aa+a=aaa,
w3 : a+aa=a

Enseignant : Fatma MLIKA et Ones SIDHOM Page 1/2


TD1 : Les enregistrements

2- En déduire le langage L (G1 ) engendré par cette grammaire.

On modifie la grammaire G1 comme suit :

𝐺1 = ({a, +, =}, {C}, C, {C → aC+a | a=a})

3- Que devient le langage L(G1 ) après cette modification ?

Exercice 4 :
Trouver pour chacune des grammaires G𝑖 = ({a, b, c}, {S, A, R, T}, P𝑖 , S)
le langage engendré par celle-ci : (i=1,..,5)

- P1: S → aS | aA; A → bAc | ε


- L(𝐏𝟏 ) = {𝒂𝒏 𝒃𝒎 𝒄𝒎 𝐩𝐨𝐮𝐫 𝐧 ≥ 𝟏; 𝐦 ≥ 𝟎}
- P2 : S → aSc | A A → bAc | ε
- L(𝐏𝟐 ) = {𝒂𝒏 𝒃𝒎 𝒄𝒏+𝒎 𝐩𝐨𝐮𝐫 𝐧, 𝐦 ≥ 𝟎}
- P3 : S → aSc | bA A → bA | ε
- L(𝐏𝟑 ) = {𝒂𝒏 𝒃𝒎 𝒄𝒏 𝐩𝐨𝐮𝐫 𝐧 ≥ 𝟎; 𝐦 ≥ 𝟏}

Exercice 5 :
Proposer (sans démonstration) une grammaire qui permet d’engendrer chacun des langages suivants :
- L1 = {𝑎𝑛 𝑏 𝑛 (𝑐|𝑑)∗ pour n ≥ 0}
S → aSb|B
B→aB|bB| ε
- L2 = {𝑎𝑛 (𝑐|𝑑)∗ 𝑏 𝑛 pour n ≥ 0}
S → aSb|A
A→aA|dA| ε
- L4 = {w {a, b, c, d} * tel que w est palindrome}. Remarque : Le mot vide est palindrome.
S →aSa | bSb | cSc | dSd | a| b |c |ε

Enseignant : Fatma MLIKA et Ones SIDHOM Page 2/2

Vous aimerez peut-être aussi