Quotient d'un langage formel - Quotient of a formal language

En mathématiques et en informatique , le quotient droit (ou simplement quotient ) d'un langage par rapport au langage est le langage composé de chaînes w telles que wx est dans pour une chaîne x dans . Officiellement: ${\style d'affichage L_{1}}$ ${\style d'affichage L_{2}}$ ${\style d'affichage L_{1}}$ ${\style d'affichage L_{2}}$

L_{1}/L_{2}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\colon \ wx\in L_{1}\}

En d'autres termes, nous prenons toutes les chaînes dans lesquelles ont un suffixe dans , et supprimons ce suffixe. ${\style d'affichage L_{1}}$ ${\style d'affichage L_{2}}$

De même, le quotient gauche de par rapport à est le langage composé de chaînes w telles que xw est dans pour une chaîne x dans . Officiellement: ${\style d'affichage L_{1}}$ ${\style d'affichage L_{2}}$ ${\style d'affichage L_{1}}$ ${\style d'affichage L_{2}}$

L_{2}\backslash L_{1}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\colon \ xw\in L_{1}\}

En d'autres termes, nous prenons toutes les chaînes dans lesquelles ont un préfixe dans , et supprimons ce préfixe. ${\style d'affichage L_{1}}$ ${\style d'affichage L_{2}}$

Notez que les opérandes de sont dans l'ordre inverse : le premier opérande est et est le second. ${\style d'affichage \ barre oblique inverse }$ ${\style d'affichage L_{2}}$ ${\style d'affichage L_{1}}$

Exemple

Considérer

L_{1}=\{a^{n}b^{n}c^{n}\mid n\geq 0\}

et

L_{2}=\{b^{i}c^{j}\mid i,j\geq 0\}.

Maintenant, si nous insérons un diviseur dans un élément de , la partie de droite n'est dans que si le diviseur est placé adjacent à a b (auquel cas i ≤ n et j = n ) ou adjacent à a c (auquel cas i = 0 et j ≤ n ). La partie de gauche sera donc soit ou ; et peut s'écrire comme ${\style d'affichage L_{1}}$ ${\style d'affichage L_{2}}$ $a^{n}b^{ni}$ $a^{n}b^{n}c^{nj}$ ${\style d'affichage L_{1}/L_{2}}$

\{\ a^{p}b^{q}c^{r}\ \mid \ p=q\geq r\ \ \lor \ \ p\geq q\land r=0\ \}.

Propriétés

Certaines propriétés de fermeture courantes de l'opération de quotient incluent :

Le quotient d'un langage régulier avec n'importe quel autre langage est régulier.
Le quotient d'un langage sans contexte avec un langage régulier est sans contexte.
Le quotient de deux langages sans contexte peut être n'importe quel langage récursivement énumérable .
Le quotient de deux langages récursivement énumérables est récursivement énumérable.

Ces propriétés de fermeture sont valables pour les quotients gauche et droit.

Voir également

dérivé de Brzozowski

Languages

In other projects

Quotient d'un langage formel - Quotient of a formal language

Contenu

Exemple

Propriétés

Voir également

Les références