Opérations sur les chaînes - String operations

En informatique , dans le domaine de la théorie du langage formel , on utilise fréquemment une variété de fonctions de chaîne ; cependant, la notation utilisée est différente de celle utilisée pour la programmation informatique , et certaines fonctions couramment utilisées dans le domaine théorique sont rarement utilisées lors de la programmation. Cet article définit certains de ces termes de base.

Chaînes et langues

Une chaîne est une séquence finie de caractères. La chaîne vide est désignée par . La concaténation de deux chaînes et est désignée par , ou plus courte par . Concaténer avec la chaîne vide ne fait aucune différence: . Concaténation de chaînes est associative : . ${\ displaystyle \ varepsilon}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle s \ cdot t}$${\ displaystyle st}$${\ displaystyle s \ cdot \ varepsilon = s = \ varepsilon \ cdot s}$${\ displaystyle s \ cdot (t \ cdot u) = (s \ cdot t) \ cdot u}$

Par exemple ,. ${\ displaystyle (\ langle b \ rangle \ cdot \ langle l \ rangle) \ cdot (\ varepsilon \ cdot \ langle ah \ rangle) = \ langle bl \ rangle \ cdot \ langle ah \ rangle = \ langle blah \ rangle}$

Une langue est un ensemble fini ou infini de chaînes. Outre les opérations d'ensembles habituelles comme l'union, l'intersection, etc., la concaténation peut être appliquée aux langues: si les deux et sont des langues, leur concaténation est définie comme l'ensemble de concaténations de toute chaîne from et de toute chaîne from , formellement . Là encore, le point de concaténation est souvent omis pour des raisons de brièveté. ${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle S \ cdot T}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle S \ cdot T = \ {s \ cdot t \ mid s \ in S \ land t \ in T \}}$${\ displaystyle \ cdot}$

La langue constituée uniquement de la chaîne vide doit être distinguée de la langue vide . Concaténer toute langue avec l'ancien ne fait pas de changement: alors que concaténer avec celui - ci donne toujours la langue vide: . Concaténation des langues est associative: . ${\ displaystyle \ {\ varepsilon \}}$${\ displaystyle \ {\}}$${\ displaystyle S \ cdot \ {\ varepsilon \} = S = \ {\ varepsilon \} \ cdot S}$${\ displaystyle S \ cdot \ {\} = \ {\} = \ {\} \ cdot S}$${\ Displaystyle S \ cdot (T \ cdot U) = (S \ cdot T) \ cdot U}$

Par exemple, en abrégé , l'ensemble de tous les nombres décimaux à trois chiffres est obtenu sous la forme . L'ensemble de tous les nombres décimaux de longueur arbitraire est un exemple de langage infini. ${\ displaystyle D = \ {\ langle 0 \ rangle, \ langle 1 \ rangle, \ langle 2 \ rangle, \ langle 3 \ rangle, \ langle 4 \ rangle, \ langle 5 \ rangle, \ langle 6 \ rangle, \ langle 7 \ rangle, \ langle 8 \ rangle, \ langle 9 \ rangle \}}$${\ Displaystyle D \ cdot D \ cdot D}$

Alphabet d'une chaîne

L' alphabet d'une chaîne est l'ensemble de tous les caractères qui apparaissent dans une chaîne particulière. Si s est une chaîne, son alphabet est noté

${\ displaystyle \ operatorname {Alph} (s)}$

L' alphabet d'une langue est l'ensemble de tous les caractères qui se produisent dans toute chaîne de formellement: . ${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle \ operatorname {Alph} (S) = \ bigcup _ {s \ in S} \ operatorname {Alph} (s)}$

Par exemple, l'ensemble est l'alphabet de la chaîne , et ce qui précède est l'alphabet de la langue ci - dessus ainsi que de la langue de tous les nombres décimaux. ${\ displaystyle \ {\ langle a \ rangle, \ langle c \ rangle, \ langle o \ rangle \}}$${\ displaystyle \ langle cacao \ rangle}$ ${\ displaystyle D}$${\ Displaystyle D \ cdot D \ cdot D}$

Substitution de chaîne

Soit L une langue , et soit Σ son alphabet. Une substitution de chaîne ou simplement une substitution est un mappage f qui mappe les caractères de Σ aux langues (éventuellement dans un alphabet différent). Ainsi, par exemple, étant donné un caractère a ∈ Σ, on a f ( a ) = L _a où L _a ⊆ Δ ^* est une langue dont l'alphabet est Δ. Ce mappage peut être étendu aux chaînes comme

f (ε) = ε

pour la chaîne vide ε, et

f ( sa ) = f ( s ) f ( a )

pour la chaîne s ∈ L et le caractère a ∈ Σ. Les substitutions de chaînes peuvent être étendues à des langues entières comme

${\ displaystyle f (L) = \ bigcup _ {s \ in L} f (s)}$

Les langues régulières sont fermées par substitution de chaîne. Autrement dit, si chaque caractère de l'alphabet d'une langue régulière est remplacé par une autre langue régulière, le résultat est toujours une langue régulière. De même, les langages sans contexte sont fermés par substitution de chaîne.

Un exemple simple est la conversion f _uc (.) En majuscules, qui peut être définie par exemple comme suit:

personnage	mappé à la langue	remarque
X	f uc ( x )
< A >	{< A >}	associer le caractère minuscule au caractère majuscule correspondant
< A >	{< A >}	mapper le caractère majuscule sur lui-même
‹ Ss ›	{‹ SS ›}	pas de caractère majuscule disponible, mapper sur une chaîne à deux caractères
‹0›	{ε}	associer un chiffre à une chaîne vide
‹!›	{}	interdire la ponctuation, mapper sur une langue vide
...		similaire pour les autres caractères

Pour l'extension de f _uc aux chaînes, nous avons par exemple

• f _uc (‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
• f _uc (‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, et
• f _uc (‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

Pour l'extension de f _uc aux langues, nous avons par exemple

• f _uc ({‹Straße›, ‹u2›, ‹Go!›}) = {‹STRASSE›} ∪ {‹U›} ∪ {} = {‹STRASSE›, ‹U›}.

Homomorphisme des cordes

Un homomorphisme de chaîne (souvent appelé simplement homomorphisme dans la théorie du langage formel ) est une substitution de chaîne telle que chaque caractère est remplacé par une seule chaîne. Autrement dit,, où est une chaîne, pour chaque caractère . ${\ displaystyle f (a) = s}$${\ displaystyle s}$${\ displaystyle a}$

Les homomorphismes de chaîne sont des morphismes monoïdes sur le monoïde libre , préservant la chaîne vide et l' opération binaire de concaténation de chaînes . Étant donné une langue , l'ensemble est appelé l' image homomorphe de . L' image homomorphe inverse d'une chaîne est définie comme ${\ displaystyle L}$${\ displaystyle f (L)}$${\ displaystyle L}$${\ displaystyle s}$

${\ Displaystyle f ^ {- 1} (s) = \ {w | f (w) = s \}}$

tandis que l'image homomorphique inverse d'une langue est définie comme ${\ displaystyle L}$

${\ displaystyle f ^ {- 1} (L) = \ {s | f (s) \ in L \}}$

En général, bien que l'on ait ${\ Displaystyle f (f ^ {- 1} (L)) \ neq L}$

${\ Displaystyle f (f ^ {- 1} (L)) \ subseteq L}$

et

${\ Displaystyle L \ subseteq f ^ {- 1} (f (L))}$

pour n'importe quelle langue . ${\ displaystyle L}$

La classe des langages réguliers est fermée sous les homomorphismes et les homomorphismes inverses. De même, les langages sans contexte sont fermés sous les homomorphismes et les homomorphismes inverses.

Un homomorphisme de chaîne est dit sans ε (ou sans e) si pour tout a dans l'alphabet . Les chiffrements de substitution à une seule lettre sont des exemples d'homomorphismes de chaîne (sans ε). ${\ displaystyle f (a) \ neq \ varepsilon}$${\ displaystyle \ Sigma}$

Un exemple d'homomorphisme de chaîne g _uc peut également être obtenu en définissant comme la substitution ci - dessus : g _uc (‹a›) = ‹A›, ..., g _uc (‹0›) = ε, mais en laissant g _uc indéfini sur les caractères de ponctuation. Des exemples d'images homomorphes inverses sont

• g _uc ⁻¹ ({‹SSS›}) = {‹sss›, ‹sß›, ‹ßs›}, puisque g _uc (‹sss›) = g _uc (‹sß›) = g _uc (‹ßs›) = ‹SSS›, et
• g _uc ⁻¹ ({‹A›, ‹bb›}) = {‹a›}, puisque g _uc (‹a›) = ‹A›, tandis que ‹bb› ne peut pas être atteint par g _uc .

Pour ce dernier langage, g _uc ( g _uc ⁻¹ ({‹A›, ‹bb›})) = g _uc ({‹a›}) = {‹A›} ≠ {‹A›, ‹bb›} . L'homomorphisme g _uc n'est pas libre de ε, puisqu'il mappe par exemple ‹0› à ε.

Un exemple d'homomorphisme de chaîne très simple qui mappe chaque caractère à un seul caractère est la conversion d'une chaîne codée EBCDIC en ASCII .

Projection de cordes

Si s est une chaîne et est un alphabet, la projection de chaîne de s est la chaîne qui résulte de la suppression de tous les caractères qui ne figurent pas dans . Il est écrit comme . Il est formellement défini par la suppression des caractères du côté droit: ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ pi _ {\ Sigma} (s) \,}$

${\ displaystyle \ pi _ {\ Sigma} (s) = {\ begin {cases} \ varepsilon & {\ mbox {if}} s = \ varepsilon {\ mbox {la chaîne vide}} \\\ pi _ {\ Sigma} (t) & {\ mbox {if}} s = ta {\ mbox {et}} a \ notin \ Sigma \\\ pi _ {\ Sigma} (t) a & {\ mbox {if}} s = ta {\ mbox {et}} a \ in \ Sigma \ end {cases}}}$

Ici dénote la chaîne vide . La projection d'une chaîne est essentiellement la même qu'une projection en algèbre relationnelle . ${\ displaystyle \ varepsilon}$

La projection de cordes peut être promue à la projection d'une langue . Etant donné un langage formel L , sa projection est donnée par

${\ displaystyle \ pi _ {\ Sigma} (L) = \ {\ pi _ {\ Sigma} (s) \ \ vert \ s \ in L \}}$

Quotient droit

Le quotient droit d'un caractère a à partir d'une chaîne s est la troncature du caractère a dans la chaîne s , à partir du côté droit. Il est noté . Si la chaîne n'a pas un sur le côté droit, le résultat est la chaîne vide. Donc: ${\ displaystyle s / a}$

${\ displaystyle (sa) / b = {\ begin {cases} s & {\ mbox {if}} a = b \\\ varepsilon & {\ mbox {if}} a \ neq b \ end {cases}}}$

Le quotient de la chaîne vide peut être pris:

${\ displaystyle \ varepsilon / a = \ varepsilon}$

De même, étant donné un sous-ensemble d'un monoïde , on peut définir le sous-ensemble de quotient comme ${\ displaystyle S \ subset M}$${\ displaystyle M}$

${\ displaystyle S / a = \ {s \ dans M \ \ vert \ sa \ dans S \}}$

Les quotients de gauche peuvent être définis de la même manière, les opérations se déroulant à gauche d'une chaîne.

Hopcroft et Ullman (1979) définissent le quotient L ₁ / L ₂ des langues L ₁ et L ₂ sur le même alphabet que L ₁ / L ₂ = { s | ∃ t ∈ L ₂ . st ∈ L ₁ }. Ce n'est pas une généralisation de la définition ci-dessus, puisque, pour une chaîne s et des caractères distincts a , b , la définition de Hopcroft et Ullman implique { sa } / { b } yielding {}, plutôt que {ε}.

Le quotient gauche (lorsqu'il est défini de manière similaire à Hopcroft et Ullman 1979) d'un langage singleton L ₁ et d'un langage arbitraire L ₂ est connu sous le nom de dérivé de Brzozowski ; si L ₂ est représenté par une expression régulière , le quotient de gauche peut également l'être.

Relation syntaxique

Le quotient droit d'un sous - ensemble d'un monoid définit une relation d'équivalence , dite droite relation syntaxique de S . Il est donné par ${\ displaystyle S \ subset M}$${\ displaystyle M}$

${\ displaystyle \ sim _ {S} \; \, = \, \ {(s, t) \ in M ​​\ times M \ \ vert \ S / s = S / t \}}$

La relation est clairement d'indice fini (a un nombre fini de classes d'équivalence) si et seulement si les quotients droits de la famille sont finis; c'est-à-dire si

${\ displaystyle \ {S / m \ \ vert \ m \ in M ​​\}}$

est fini. Dans le cas où M est le monoïde des mots sur un alphabet, S est alors une langue régulière , c'est-à-dire une langue qui peut être reconnue par un automate à états finis . Ceci est discuté plus en détail dans l'article sur les monoïdes syntaxiques .

Droit d'annulation

La bonne annulation d'un caractère a d'une chaîne s est la suppression de la première occurrence du caractère a dans la chaîne s , en commençant par le côté droit. Il est noté et est défini de manière récursive comme ${\ displaystyle s \ div a}$

${\ displaystyle (sa) \ div b = {\ begin {cases} s & {\ mbox {if}} a = b \\ (s \ div b) a & {\ mbox {if}} a \ neq b \ end { cas}}}$

La chaîne vide est toujours annulable:

${\ displaystyle \ varepsilon \ div a = \ varepsilon}$

Clairement, annulation correcte et trajet de projection :

${\ displaystyle \ pi _ {\ Sigma} (s) \ div a = \ pi _ {\ Sigma} (s \ div a)}$

Préfixes

Les préfixes d'une chaîne sont l'ensemble de tous les préfixes d'une chaîne, par rapport à une langue donnée:

${\ displaystyle \ operatorname {Pref} _ {L} (s) = \ {t \ \ vert \ s = tu {\ mbox {for}} t, u \ in \ operatorname {Alph} (L) ^ {*} \}}$

où . ${\ displaystyle s \ in L}$

Le préfixe de fermeture d'une langue est

${\ displaystyle \ operatorname {Pref} (L) = \ bigcup _ {s \ in L} \ operatorname {Pref} _ {L} (s) = \ left \ {t \ \ vert \ s = tu; s \ in L; t, u \ in \ operatorname {Alph} (L) ^ {*} \ right \}}$

Exemple:
${\ displaystyle L = \ left \ {abc \ right \} {\ mbox {then}} \ operatorname {Pref} (L) = \ left \ {\ varepsilon, a, ab, abc \ right \}}$

Une langue est appelée préfixe fermé si . ${\ displaystyle \ operatorname {Pref} (L) = L}$

L'opérateur de fermeture du préfixe est idempotent :

${\ displaystyle \ operatorname {Pref} (\ operatorname {Pref} (L)) = \ operatorname {Pref} (L)}$

La relation de préfixe est une relation binaire telle que si et seulement si . Cette relation est un exemple particulier d' ordre de préfixe . ${\ displaystyle \ sqsubseteq}$${\ displaystyle s \ sqsubseteq t}$${\ displaystyle s \ in \ operatorname {Pref} _ {L} (t)}$

Voir également

• Comparaison des langages de programmation (fonctions de chaîne)
• Lemme de Levi
• String (informatique) - définition et implémentation d'opérations plus basiques sur les chaînes

Remarques

Les références

• Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introduction à la théorie des automates, aux langages et au calcul . Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl  0426.68001 . (Voir chapitre 3.)