Théorie des Languages

Question 1

Donner un schéma de l’ordre d’inclusion des langages formels selon la hiérarchie de Chomsky

Answer 1

Question 2

Qu’est ce qu’un langage formel?

Answer 2

Un langage formel est un ensemble (fini ou infini) de mots

Question 3

Qu’est-ce qu’un mot pour un langage?

Answer 3

un mot est une suite finie de symboles provenant d’un alphabet donné. Le mot vide (noté epsilon) ne contient aucun symbole

Question 4

qu’est qu’un alphabet ?

Answer 4

alphabet (souvent noté A ou Σ) contient un nombre fini de symboles

Question 5

À quoi sert la hiérarchie de Chomsky ?

Answer 5

Elle classe les langages en quatre types selon leur puissance expressive et complexité : langages rationnels (type 3), langages algébriques (type 2), langages contextuels (type 1) et langages récursivement énumérables (type 0).

Question 6

Qu’est-ce qu’une grammaire en théorie des langages formels ?

Answer 6

Une grammaire est un formalisme utilisé pour représenter un langage FORMEL, comprenant des symboles terminaux( minuscules), non-terminaux (MAJUSCULES), un symbole de départ et des règles de production.

Question 6

Qu’est-ce que la concaténation dans les opérations sur les langages ?

Answer 6

Question 7

Qu’est ce que l’opération de puissance d’un langage ?

Answer 7

Question 7

expliquer ce tableau de clôture des langages

Answer 7

Ce tableau démontre comment chaque type de langage réagit à ces opérations, indiquant si l’application d’une opération spécifique sur des langages d’un certain type résulte toujours en un langage du même type.

Question 7

Qu’est que la la fermeture de Kleene ?

Answer 7

Question 7

Qu’est-ce qu’une grammaire linéaire ?

Answer 7

• non contextuelle( ou algébrique)
• membre droit possède des terminaux et au max un non terminal

Question 8

Qu’est-ce qu’une grammaire linéaire à gauche ?

Answer 8

Une grammaire est linéaire a gauche si
-c’est une grammaire linéaire
- et le non terminal de la partie droite est le premier élément(à gauche) : A → Bc

Une grammaire linéaire a gauche permet représenter un langage rationnel (type 3)
ATTENTION pas de linéaire a gauche et a droite sinon pas rationnel

Question 9

Qu’est-ce qu’une grammaire linéaire à droite ?

Answer 9

Une grammaire est linéaire a droite si
-c’est une grammaire linéaire
- et le non terminal de la partie droite est le dernier élément(à droite) : A → cB

Une grammaire linéaire a droite permet représenter un langage rationnel (type 3)
ATTENTION pas de linéaire a gauche et a droite sinon pas rationnel

Question 10

Qu’est ce qu’une grammaire contextuelle ?

Answer 10

Question 11

Qu’est ce qu’une grammaire non contextuelle (ou algébrique) ?

Answer 11