^{PDFprof.com Search Engine}

Langages Formels

Comment montrer qu'un langage est algébrique ?
Un langage est dit algébrique s'il peut être en- gendré par une grammaire, c'est-à-dire s'il est égal à LG(S) pour une variable S d'une grammaire G.
Exemple 2.7.
Soit G la grammaire donnée à l'exemple 2.2.
Le langage LG(S) est égal à {anbn n ≥ 0} qui est donc un langage algébrique.
Comment montrer qu'un langage n'est pas reconnaissable ?
Pour montrer qu'un langage n'est pas reconnaissable, on peut aussi utiliser les propriétés de clôture.
Exemples : Sachant que L1 n'est pas reconnaissable.
L2 ∩ a∗b∗ = L1.
Donc L2 n'est pas reconnaissable.
Quel est l'intérêt de la théorie des langages pour la compilation ?
La théorie des langages fournit une base conceptuelle et éventuellement des outils de production qui réduisent considérablement les coûts de production des modules « analyseur syntaxique » et « décompilateur ».
La définition rigoureuse des arbres abstraits manipulés facilite la conception du « cœur » de l'application.
Le langage engendré par une grammaire algébrique (Σ,N,P,S) est l'ensemble des mots de Σ∗ qui se dérive de S par la grammaire.
Exemple : le langage des mots bien parenthésés est engendré par la grammaire Gbp.
Un langage est dit algébrique s'il existe une grammaire algébrique qui l'engendre.

Comment montrer qu'un langage est algébrique ?