Grammaire algébrique — Les-mathematiques.net The most powerful custom community solution in the world

Grammaire algébrique

Modifié (November 2022) dans Algèbre
Bonjour à tous
Dans le cadre de mes études en informatique, j'ai suivi un cours il y a longtemps sur les langages de programmation où il était question de "mettre la grammaire en équation".
Ex :
$S → a | b$ autorise les mots $a$ et $b$.
$S → Sa | b$ autorise $b$, $ba$, $baa$, $baaa$ ... et plut généralement $ba^*$.
L'opérateur $|$ agit comme une union tandis que $.$ agit comme une concaténation ($ab ≠ ba$).
$S → a | a ⇒ S → a$
Cependant, si on remplace $|$ et $.$ respectivement par $+$ et $\times$ dans le dernier exemple du premier paragraphe, on obtient :
$S = Sa + b$
$S - Sa = b$
$S (1 - a) = b$
$S = b . \frac{1}{1 - a}$
Or, le développement limité de $\frac{1}{1 - a}$ donne $1 + a + a^2 + a^3 ...$ et on retombe bien sur $S → ba^*$.
Ma question est la suivante.
A priori, les opérateurs $|$ et $.$ ne doivent pas être confondus avec $+$ et $\times$. Dans ce cas comment se fait-il que la formule du développement limité fonctionne si bien ?

Réponses

  • Bonjour, pronodingo,
    ici, $S=Sa+b$ entre dans un cas particulier du lemme d'Arden ($X=AX+B$, lorsque $\varepsilon\not\in A$ : la même remarque se fait alors), mais je n'ai jamais rencontré de situation beaucoup plus générale ; on peut toutefois le généraliser au cas où $A$ est une matrice carrée de langages et où $A$ et $B$ des vecteurs colonnes de langages.

    Tu n'as pas écrit languages ; c'est bien, je te félicite :)
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!