Opérations sur les chaînes

En informatique , dans le domaine de la théorie des langages formels , 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 en programmation. Cet article définit certains de ces termes de base.

Chaînes et langages

Une chaîne est une séquence finie de caractères. La chaîne vide est notée . La concaténation de deux chaînes et est notée , ou plus court . La concaténation avec la chaîne vide ne fait aucune différence : . La concaténation de chaînes est associative : . ${\displaystyle \varepsilon <semantics> <mrow> <mstyle> <mi>ε</mi> </mstyle> </mrow> <annotation>{\displaystyle \varepsilon }</annotation> </semantics> </math><img src=$ ${\displaystyle s <semantics> <mrow> <mstyle> <mi>m</mi> </mstyle> </mrow> <annotation>{\style d'affichage s}</annotation> </semantics> </math><img src=$ ${\displaystyle t <semantics> <mrow> <mstyle> <mi>t</mi> </mstyle> </mrow> <annotation>{\displaystyle t}</annotation> </semantics> </math><img src=$ ${\displaystyle s\cdot t <semantics> <mrow> <mstyle> <mi>m</mi> <mo>⋅</mo> <mi>t</mi> </mstyle> </mrow> <annotation>{\displaystyle s\cdot t}</annotation> </semantics> </math><img src=$ ${\displaystyle st <semantics> <mrow> <mstyle> <mi>m</mi> <mi>t</mi> </mstyle> </mrow> <annotation>{\displaystyle st}</annotation> </semantics> </math><img src=$ ${\displaystyle s\cdot \varepsilon =s=\varepsilon \cdot s <semantics> <mrow> <mstyle> <mi>m</mi> <mo>⋅</mo> <mi>ε</mi> <mo>=</mo> <mi>m</mi> <mo>=</mo> <mi>ε</mi> <mo>⋅</mo> <mi>m</mi> </mstyle> </mrow> <annotation>{\displaystyle s\cdot \varepsilon =s=\varepsilon \cdot s}</annotation> </semantics> </math><img src=$ ${\displaystyle s\cdot (t\cdot u)=(s\cdot t)\cdot u <semantics> <mrow> <mstyle> <mi>m</mi> <mo>⋅</mo> <mo>(</mo> <mi>t</mi> <mo>⋅</mo> <mi>toi</mi> <mo>)</mo> <mo>=</mo> <mo>(</mo> <mi>m</mi> <mo>⋅</mo> <mi>t</mi> <mo>)</mo> <mo>⋅</mo> <mi>toi</mi> </mstyle> </mrow> <annotation>{\displaystyle s\cdot (t\cdot u)=(s\cdot t)\cdot u}</annotation> </semantics> </math><img src=$

Par exemple, . ${\displaystyle (\langle b angle \cdot \langle l angle )\cdot (\varepsilon \cdot \langle ah angle )=\langle bl angle \cdot \langle ah angle =\langle blah angle <semantics> <mrow> <mstyle> <mo>(</mo> <mo>⟨</mo> <mi>b</mi> <mo>⟩</mo> <mo>⋅</mo> <mo>⟨</mo> <mi>l</mi> <mo>⟩</mo> <mo>)</mo> <mo>⋅</mo> <mo>(</mo> <mi>ε</mi> <mo>⋅</mo> <mo>⟨</mo> <mi>un</mi> <mi>h</mi> <mo>⟩</mo> <mo>)</mo> <mo>=</mo> <mo>⟨</mo> <mi>b</mi> <mi>l</mi> <mo>⟩</mo> <mo>⋅</mo> <mo>⟨</mo> <mi>un</mi> <mi>h</mi> <mo>⟩</mo> <mo>=</mo> <mo>⟨</mo> <mi>b</mi> <mi>l</mi> <mi>un</mi> <mi>h</mi> <mo>⟩</mo> </mstyle> </mrow> <annotation>{\displaystyle (\langle b angle \cdot \langle l angle )\cdot (\varepsilon \cdot \langle ah angle )=\langle bl angle \cdot \langle ah angle =\langle blah angle }</annotation> </semantics> </math><img src=$

Un langage est un ensemble fini ou infini de chaînes de caractères. Outre les opérations d'ensemble habituelles telles que l'union, l'intersection, etc., la concaténation peut être appliquée aux langages : si et sont des langages, leur concaténation est définie comme l'ensemble des concaténations de toute chaîne de et de toute chaîne de , formellement . Là encore, le point de concaténation est souvent omis par souci de concision. ${\displaystyle S <semantics> <mrow> <mstyle> <mi>S</mi> </mstyle> </mrow> <annotation>{\displaystyle S}</annotation> </semantics> </math><img src=$ ${\displaystyle T <semantics> <mrow> <mstyle> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle T}</annotation> </semantics> </math><img src=$ ${\displaystyle S\cdot T <semantics> <mrow> <mstyle> <mi>S</mi> <mo>⋅</mo> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle S\cdot T}</annotation> </semantics> </math><img src=$ ${\displaystyle S <semantics> <mrow> <mstyle> <mi>S</mi> </mstyle> </mrow> <annotation>{\displaystyle S}</annotation> </semantics> </math><img src=$ ${\displaystyle T <semantics> <mrow> <mstyle> <mi>T</mi> </mstyle> </mrow> <annotation>{\displaystyle T}</annotation> </semantics> </math><img src=$ ${\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\ <semantics> <mrow> <mstyle> <mi>S</mi> <mo>⋅</mo> <mi>T</mi> <mo>=</mo> <mo>{</mo> <mi>m</mi> <mo>⋅</mo> <mi>t</mi> <mo>∣</mo> <mi>m</mi> <mo>∈</mo> <mi>S</mi> <mo>∧</mo> <mi>t</mi> <mo>∈</mo> <mi>T</mi> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}}</annotation> </semantics> </math><img src=$ ${\displaystyle \cdot <semantics> <mrow> <mstyle> <mo>⋅</mo> </mstyle> </mrow> <annotation>{\displaystyle \cdot }</annotation> </semantics> </math><img src=$

Le langage constitué uniquement de la chaîne vide doit être distingué du langage vide . Concaténer un langage quelconque avec le premier n'apporte aucun changement : , tandis que concaténer avec le second produit toujours le langage vide : . La concaténation des langages est associative : . ${\displaystyle \{\varepsilon \ <semantics> <mrow> <mstyle> <mo>{</mo> <mi>ε</mi> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{\varepsilon \}}</annotation> </semantics> </math><img src=$ ${\displaystyle \{\ <semantics> <mrow> <mstyle> <mo>{</mo> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{\}}</annotation> </semantics> </math><img src=$ ${\displaystyle S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S <semantics> <mrow> <mstyle> <mi>S</mi> <mo>⋅</mo> <mo>{</mo> <mi>ε</mi> <mo>}</mo> <mo>=</mo> <mi>S</mi> <mo>=</mo> <mo>{</mo> <mi>ε</mi> <mo>}</mo> <mo>⋅</mo> <mi>S</mi> </mstyle> </mrow> <annotation>{\displaystyle S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S}</annotation> </semantics> </math><img src=$ ${\displaystyle S\cdot \{\}=\{\}=\{\}\cdot S <semantics> <mrow> <mstyle> <mi>S</mi> <mo>⋅</mo> <mo>{</mo> <mo>}</mo> <mo>=</mo> <mo>{</mo> <mo>}</mo> <mo>=</mo> <mo>{</mo> <mo>}</mo> <mo>⋅</mo> <mi>S</mi> </mstyle> </mrow> <annotation>{\displaystyle S\cdot \{\}=\{\}=\{\}\cdot S}</annotation> </semantics> </math><img src=$ ${\displaystyle S\cdot (T\cdot U)=(S\cdot T)\cdot U <semantics> <mrow> <mstyle> <mi>S</mi> <mo>⋅</mo> <mo>(</mo> <mi>T</mi> <mo>⋅</mo> <mi>U</mi> <mo>)</mo> <mo>=</mo> <mo>(</mo> <mi>S</mi> <mo>⋅</mo> <mi>T</mi> <mo>)</mo> <mo>⋅</mo> <mi>U</mi> </mstyle> </mrow> <annotation>{\displaystyle S\cdot (T\cdot U)=(S\cdot T)\cdot U}</annotation> </semantics> </math><img src=$

Par exemple, en abrégeant , l'ensemble de tous les nombres décimaux à trois chiffres est obtenu comme . L'ensemble de tous les nombres décimaux de longueur arbitraire est un exemple de langage infini. ${\displaystyle D=\{\langle 0 angle ,\langle 1 angle ,\langle 2 angle ,\langle 3 angle ,\langle 4 angle ,\langle 5 angle ,\langle 6 angle ,\langle 7 angle ,\langle 8 angle ,\langle 9 angle \ <semantics> <mrow> <mstyle> <mi>D</mi> <mo>=</mo> <mo>{</mo> <mo>⟨</mo> <mn>0</mn> <mo>⟩</mo> <mo>,</mo> <mo>⟨</mo> <mn>1</mn> <mo>⟩</mo> <mo>,</mo> <mo>⟨</mo> <mn>2</mn> <mo>⟩</mo> <mo>,</mo> <mo>⟨</mo> <mn>3</mn> <mo>⟩</mo> <mo>,</mo> <mo>⟨</mo> <mn>4</mn> <mo>⟩</mo> <mo>,</mo> <mo>⟨</mo> <mn>5</mn> <mo>⟩</mo> <mo>,</mo> <mo>⟨</mo> <mn>6</mn> <mo>⟩</mo> <mo>,</mo> <mo>⟨</mo> <mn>7</mn> <mo>⟩</mo> <mo>,</mo> <mo>⟨</mo> <mn>8</mn> <mo>⟩</mo> <mo>,</mo> <mo>⟨</mo> <mn>9</mn> <mo>⟩</mo> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle D=\{\langle 0 angle ,\langle 1 angle ,\langle 2 angle ,\langle 3 angle ,\langle 4 angle ,\langle 5 angle ,\langle 6 angle ,\langle 7 angle ,\langle 8 angle ,\langle 9 angle \}}</annotation> </semantics> </math><img src=$ ${\displaystyle D\cdot D\cdot D <semantics> <mrow> <mstyle> <mi>D</mi> <mo>⋅</mo> <mi>D</mi> <mo>⋅</mo> <mi>D</mi> </mstyle> </mrow> <annotation>{\displaystyle D\cdot D\cdot D}</annotation> </semantics> </math><img src=$

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 indiqué par

{\displaystyle \operatorname {Alph} (s) <semantics> <mrow> <mstyle> <mi>Alph</mi> <mo>⁡</mo> <mo>(</mo> <mi>s</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle \operatorname {Alph} (s)}</annotation> </semantics> </math></span><img src=

L' alphabet d'une langue est l'ensemble de tous les caractères qui apparaissent dans n'importe quelle chaîne de , formellement : . ${\displaystyle S <semantics> <mrow> <mstyle> <mi>S</mi> </mstyle> </mrow> <annotation>{\displaystyle S}</annotation> </semantics> </math><img src=$ ${\displaystyle S <semantics> <mrow> <mstyle> <mi>S</mi> </mstyle> </mrow> <annotation>{\displaystyle S}</annotation> </semantics> </math><img src=$ ${\displaystyle \operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s) <semantics> <mrow> <mstyle> <mi>Alph</mi> <mo>⁡</mo> <mo>(</mo> <mi>S</mi> <mo>)</mo> <mo>=</mo> <munder> <mo>⋃</mo> <mrow> <mi>s</mi> <mo>∈</mo> <mi>S</mi> </mrow> </munder> <mi>Alph</mi> <mo>⁡</mo> <mo>(</mo> <mi>s</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle \operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)}</annotation> </semantics> </math><img src=$

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 angle ,\langle c angle ,\langle o angle \ <semantics> <mrow> <mstyle> <mo>{</mo> <mo>⟨</mo> <mi>a</mi> <mo>⟩</mo> <mo>,</mo> <mo>⟨</mo> <mi>c</mi> <mo>⟩</mo> <mo>,</mo> <mo>⟨</mo> <mi>o</mi> <mo>⟩</mo> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{\langle a angle ,\langle c angle ,\langle o angle \}}</annotation> </semantics> </math><img src=$ ${\displaystyle \langle cacao angle <semantics> <mrow> <mstyle> <mo>⟨</mo> <mi>c</mi> <mi>a</mi> <mi>c</mi> <mi>a</mi> <mi>o</mi> <mo>⟩</mo> </mstyle> </mrow> <annotation>{\displaystyle \langle cacao angle }</annotation> </semantics> </math><img src=$ ${\displaystyle D <semantics> <mrow> <mstyle> <mi>D</mi> </mstyle> </mrow> <annotation>{\displaystyle D}</annotation> </semantics> </math><img src=$ ${\displaystyle D\cdot D\cdot D <semantics> <mrow> <mstyle> <mi>D</mi> <mo>⋅</mo> <mi>D</mi> <mo>⋅</mo> <mi>D</mi> </mstyle> </mrow> <annotation>{\displaystyle D\cdot D\cdot D}</annotation> </semantics> </math><img src=$

Substitution de chaîne

Soit L une langue et Σ son alphabet. Une substitution de chaîne ou simplement une substitution est une application f qui associe des caractères de Σ à des 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 Δ. Cette application peut être étendue 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 langages entiers comme

{\displaystyle f(L)=\bigcup _{s\in L}f(s) <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>L</mi> <mo>)</mo> <mo>=</mo> <munder> <mo>⋃</mo> <mrow> <mi>s</mi> <mo>∈</mo> <mi>L</mi> </mrow> </munder> <mi>f</mi> <mo>(</mo> <mi>s</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle f(L)=\bigcup _{s\in L}f(s)}</annotation> </semantics> </math></span><img src=

Les langages réguliers sont fermés en cas de substitution de chaîne. Autrement dit, si chaque caractère de l'alphabet d'un langage régulier est remplacé par un autre langage régulier, le résultat est toujours un langage régulier. De même, les langages sans contexte sont fermés en cas de substitution de chaîne.

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

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

f _uc (‹Street›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
f _uc (‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, et
f _uc (‹Allez !›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

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

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

Homomorphisme de chaîne

Un homomorphisme de chaîne (souvent appelé simplement homomorphisme dans la théorie formelle du langage ) est une substitution de chaîne telle que chaque caractère est remplacé par une seule chaîne. C'est-à-dire, , où est une chaîne, pour chaque caractère . ${\displaystyle f(a)=s <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>a</mi> <mo>)</mo> <mo>=</mo> <mi>s</mi> </mstyle> </mrow> <annotation>{\displaystyle f(a)=s}</annotation> </semantics> </math><img src=$ ${\displaystyle s <semantics> <mrow> <mstyle> <mi>s</mi> </mstyle> </mrow> <annotation>{\displaystyle s}</annotation> </semantics> </math><img src=$ ${\displaystyle a <semantics> <mrow> <mstyle> <mi>a</mi> </mstyle> </mrow> <annotation>{\displaystyle a}</annotation> </semantics> </math><img src=$

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îne . Étant donné un langage , l'ensemble est appelé l' image homomorphe de . L' image homomorphe inverse d'une chaîne est définie comme ${\displaystyle L <semantics> <mrow> <mstyle> <mi>L</mi> </mstyle> </mrow> <annotation>{\displaystyle L}</annotation> </semantics> </math><img src=$ ${\displaystyle f(L) <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>L</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle f(L)}</annotation> </semantics> </math><img src=$ ${\displaystyle L <semantics> <mrow> <mstyle> <mi>L</mi> </mstyle> </mrow> <annotation>{\displaystyle L}</annotation> </semantics> </math><img src=$ ${\displaystyle s <semantics> <mrow> <mstyle> <mi>s</mi> </mstyle> </mrow> <annotation>{\displaystyle s}</annotation> </semantics> </math><img src=$

${\displaystyle f^{-1}(s)=\{w\mid f(w)=s\ <semantics> <mrow> <mstyle> <msup> <mi>f</mi> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>(</mo> <mi>s</mi> <mo>)</mo> <mo>=</mo> <mo>{</mo> <mi>w</mi> <mo>∣</mo> <mi>f</mi> <mo>(</mo> <mi>w</mi> <mo>)</mo> <mo>=</mo> <mi>s</mi> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle f^{-1}(s)=\{w\mid f(w)=s\}}</annotation> </semantics> </math><img src=$

tandis que l'image homomorphe inverse d'une langue est définie comme ${\displaystyle L <semantics> <mrow> <mstyle> <mi>L</mi> </mstyle> </mrow> <annotation>{\displaystyle L}</annotation> </semantics> </math><img src=$

${\displaystyle f^{-1}(L)=\{s\mid f(s)\in L\ <semantics> <mrow> <mstyle> <msup> <mi>f</mi> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>(</mo> <mi>L</mi> <mo>)</mo> <mo>=</mo> <mo>{</mo> <mi>s</mi> <mo>∣</mo> <mi>f</mi> <mo>(</mo> <mi>s</mi> <mo>)</mo> <mo>∈</mo> <mi>L</mi> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle f^{-1}(L)=\{s\mid f(s)\in L\}}</annotation> </semantics> </math><img src=$

En général, , bien que l'on ait ${\displaystyle f(f^{-1}(L)) eq L <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <msup> <mi>f</mi> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>(</mo> <mi>L</mi> <mo>)</mo> <mo>)</mo> <mo>≠</mo> <mi>L</mi> </mstyle> </mrow> <annotation>{\displaystyle f(f^{-1}(L)) eq L}</annotation> </semantics> </math><img src=$

${\displaystyle f(f^{-1}(L))\subseteq L <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <msup> <mi>f</mi> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>(</mo> <mi>L</mi> <mo>)</mo> <mo>)</mo> <mo>⊆</mo> <mi>L</mi> </mstyle> </mrow> <annotation>{\displaystyle f(f^{-1}(L))\subseteq L}</annotation> </semantics> </math><img src=$

${\displaystyle L\subseteq f^{-1}(f(L)) <semantics> <mrow> <mstyle> <mi>L</mi> <mo>⊆</mo> <msup> <mi>f</mi> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>(</mo> <mi>f</mi> <mo>(</mo> <mi>L</mi> <mo>)</mo> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle L\subseteq f^{-1}(f(L))}</annotation> </semantics> </math><img src=$

pour n'importe quelle langue . ${\displaystyle L <semantics> <mrow> <mstyle> <mi>L</mi> </mstyle> </mrow> <annotation>{\displaystyle L}</annotation> </semantics> </math><img src=$

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 ε-libre (ou e-libre) si pour tout a de l'alphabet . Les chiffrements simples de substitution à une seule lettre sont des exemples d'homomorphismes de chaîne (ε-libres). ${\displaystyle f(a) eq \varepsilon <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>a</mi> <mo>)</mo> <mo>≠</mo> <mi>ε</mi> </mstyle> </mrow> <annotation>{\displaystyle f(a) eq \varepsilon }</annotation> </semantics> </math><img src=$ ${\displaystyle \Sigma <semantics> <mrow> <mstyle> <mi>Σ</mi> </mstyle> </mrow> <annotation>{\displaystyle \Sigma }</annotation> </semantics> </math><img src=$

Un exemple d'homomorphisme de chaîne g _uc peut également être obtenu en définissant de manière similaire à 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, car il mappe par exemple ‹0› sur ε.

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

Projection de corde

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 sont pas dans . Elle s'écrit . Elle est formellement définie par la suppression des caractères du côté droit : ${\displaystyle \Sigma <semantics> <mrow> <mstyle> <mi>Σ</mi> </mstyle> </mrow> <annotation>{\displaystyle \Sigma }</annotation> </semantics> </math><img src=$ ${\displaystyle \Sigma <semantics> <mrow> <mstyle> <mi>Σ</mi> </mstyle> </mrow> <annotation>{\displaystyle \Sigma }</annotation> </semantics> </math><img src=$ ${\displaystyle \pi _{\Sigma }(s)\, <semantics> <mrow> <mstyle> <msub> <mi>π</mi> <mrow> <mi>Σ</mi> </mrow> </msub> <mo>(</mo> <mi>s</mi> <mo>)</mo> <mspace></mspace> </mstyle> </mrow> <annotation>{\displaystyle \pi _{\Sigma }(s)\,}</annotation> </semantics> </math><img src=$

{\displaystyle \pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty string}}\\\pi _{\Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a otin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases <semantics> <mrow> <mstyle> <msub> <mi>π</mi> <mrow> <mi>Σ</mi> </mrow> </msub> <mo>(</mo> <mi>s</mi> <mo>)</mo> <mo>=</mo> <mrow> <mrow> <mo>{</mo> <mtable> <mtr> <mtd> <mi>ε</mi> </mtd> <mtd> <mrow> <mstyle> <mtext>if </mtext> </mstyle> </mrow> <mi>s</mi> <mo>=</mo> <mi>ε</mi> <mrow> <mstyle> <mtext> the empty string</mtext> </mstyle> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>π</mi> <mrow> <mi>Σ</mi> </mrow> </msub> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mtd> <mtd> <mrow> <mstyle> <mtext>if </mtext> </mstyle> </mrow> <mi>s</mi> <mo>=</mo> <mi>t</mi> <mi>a</mi> <mrow> <mstyle> <mtext> and </mtext> </mstyle> </mrow> <mi>a</mi> <mo>∉</mo> <mi>Σ</mi> </mtd> </mtr> <mtr> <mtd> <msub> <mi>π</mi> <mrow> <mi>Σ</mi> </mrow> </msub> <mo>(</mo> <mi>t</mi> <mo>)</mo> <mi>a</mi> </mtd> <mtd> <mrow> <mstyle> <mtext>if </mtext> </mstyle> </mrow> <mi>s</mi> <mo>=</mo> <mi>t</mi> <mi>a</mi> <mrow> <mstyle> <mtext> and </mtext> </mstyle> </mrow> <mi>a</mi> <mo>∈</mo> <mi>Σ</mi> </mtd> </mtr> </mtable> <mo></mo> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty string}}\\\pi _{\Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a otin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases}}}</annotation> </semantics> </math></span><img src=

Ici désigne la chaîne vide . La projection d'une chaîne est essentiellement la même qu'une projection en algèbre relationnelle . ${\displaystyle \varepsilon <semantics> <mrow> <mstyle> <mi>ε</mi> </mstyle> </mrow> <annotation>{\displaystyle \varepsilon }</annotation> </semantics> </math><img src=$

La projection de chaîne peut être promue à la projection d'un langage . Étant donné un langage formel L , sa projection est donnée par

{\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\ <semantics> <mrow> <mstyle> <msub> <mi>π</mi> <mrow> <mi>Σ</mi> </mrow> </msub> <mo>(</mo> <mi>L</mi> <mo>)</mo> <mo>=</mo> <mo>{</mo> <msub> <mi>π</mi> <mrow> <mi>Σ</mi> </mrow> </msub> <mo>(</mo> <mi>s</mi> <mo>)</mo> <mtext> </mtext> <mo>|</mo> <mtext> </mtext> <mi>s</mi> <mo>∈</mo> <mi>L</mi> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}}</annotation> </semantics> </math></span><img src=

Quotient droit et gauche

Le quotient droit d'un caractère a 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 de a sur le côté droit, le résultat est la chaîne vide. Ainsi : ${\displaystyle s/a <semantics> <mrow> <mstyle> <mi>s</mi> <mrow> <mo>/</mo> </mrow> <mi>a</mi> </mstyle> </mrow> <annotation>{\displaystyle s/a}</annotation> </semantics> </math><img src=$

{\displaystyle (sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a eq b\end{cases <semantics> <mrow> <mstyle> <mo>(</mo> <mi>s</mi> <mi>a</mi> <mo>)</mo> <mrow> <mo>/</mo> </mrow> <mi>b</mi> <mo>=</mo> <mrow> <mrow> <mo>{</mo> <mtable> <mtr> <mtd> <mi>s</mi> </mtd> <mtd> <mrow> <mstyle> <mtext>if </mtext> </mstyle> </mrow> <mi>a</mi> <mo>=</mo> <mi>b</mi> </mtd> </mtr> <mtr> <mtd> <mi>ε</mi> </mtd> <mtd> <mrow> <mstyle> <mtext>if </mtext> </mstyle> </mrow> <mi>a</mi> <mo>≠</mo> <mi>b</mi> </mtd> </mtr> </mtable> <mo></mo> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle (sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a eq b\end{cases}}}</annotation> </semantics> </math></span><img src=

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

{\displaystyle \varepsilon /a=\varepsilon <semantics> <mrow> <mstyle> <mi>ε</mi> <mrow> <mo>/</mo> </mrow> <mi>a</mi> <mo>=</mo> <mi>ε</mi> </mstyle> </mrow> <annotation>{\displaystyle \varepsilon /a=\varepsilon }</annotation> </semantics> </math></span><img src=

De même, étant donné un sous-ensemble d'un monoïde , on peut définir le sous-ensemble quotient comme ${\displaystyle S\subset M <semantics> <mrow> <mstyle> <mi>S</mi> <mo>⊂</mo> <mi>M</mi> </mstyle> </mrow> <annotation>{\displaystyle S\subset M}</annotation> </semantics> </math><img src=$ ${\displaystyle M <semantics> <mrow> <mstyle> <mi>M</mi> </mstyle> </mrow> <annotation>{\displaystyle M}</annotation> </semantics> </math><img src=$

{\displaystyle S/a=\{s\in M\ \vert \ sa\in S\ <semantics> <mrow> <mstyle> <mi>S</mi> <mrow> <mo>/</mo> </mrow> <mi>a</mi> <mo>=</mo> <mo>{</mo> <mi>s</mi> <mo>∈</mo> <mi>M</mi> <mtext> </mtext> <mo>|</mo> <mtext> </mtext> <mi>s</mi> <mi>a</mi> <mo>∈</mo> <mi>S</mi> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle S/a=\{s\in M\ \vert \ sa\in S\}}</annotation> </semantics> </math></span><img src=

Les quotients gauches 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 comme L ₁ / L ₂ = { s | ∃ t ∈ L ₂ . st ∈ L ₁ } . Il ne s'agit pas d'une généralisation de la définition ci-dessus, car, pour une chaîne s et des caractères distincts a , b , la définition de Hopcroft et Ullman impliquedonnant {}, 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ée de Brzozowski ; si L ₂ est représenté par une expression régulière , il peut en être de même pour le quotient gauche.

Relation syntaxique

Le quotient droit d'un sous-ensemble d'un monoïde définit une relation d'équivalence , appelée relation syntaxique droite de S. Elle est donnée par ${\displaystyle S\subset M <semantics> <mrow> <mstyle> <mi>S</mi> <mo>⊂</mo> <mi>M</mi> </mstyle> </mrow> <annotation>{\displaystyle S\subset M}</annotation> </semantics> </math><img src=$ ${\displaystyle M <semantics> <mrow> <mstyle> <mi>M</mi> </mstyle> </mrow> <annotation>{\displaystyle M}</annotation> </semantics> </math><img src=$

{\displaystyle \sim _{S}\;\,=\,\{(s,t)\in M imes M\ \vert \ S/s=S/t\ <semantics> <mrow> <mstyle> <msub> <mo>∼</mo> <mrow> <mi>S</mi> </mrow> </msub> <mspace></mspace> <mspace></mspace> <mo>=</mo> <mspace></mspace> <mo>{</mo> <mo>(</mo> <mi>s</mi> <mo>,</mo> <mi>t</mi> <mo>)</mo> <mo>∈</mo> <mi>M</mi> <mo>×</mo> <mi>M</mi> <mtext> </mtext> <mo>|</mo> <mtext> </mtext> <mi>S</mi> <mrow> <mo>/</mo> </mrow> <mi>s</mi> <mo>=</mo> <mi>S</mi> <mrow> <mo>/</mo> </mrow> <mi>t</mi> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \sim _{S}\;\,=\,\{(s,t)\in M imes M\ \vert \ S/s=S/t\}}</annotation> </semantics> </math></span><img src=

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\ <semantics> <mrow> <mstyle> <mo>{</mo> <mi>S</mi> <mrow> <mo>/</mo> </mrow> <mi>m</mi> <mtext> </mtext> <mo>|</mo> <mtext> </mtext> <mi>m</mi> <mo>∈</mo> <mi>M</mi> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{S/m\ \vert \ m\in M\}}</annotation> </semantics> </math></span><img src=

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

Annulation du droit

L' annulation à droite 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. Elle est notée et est définie de manière récursive comme ${\displaystyle s\div a <semantics> <mrow> <mstyle> <mi>s</mi> <mo>÷</mo> <mi>a</mi> </mstyle> </mrow> <annotation>{\displaystyle s\div a}</annotation> </semantics> </math><img src=$

{\displaystyle (sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a eq b\end{cases <semantics> <mrow> <mstyle> <mo>(</mo> <mi>s</mi> <mi>a</mi> <mo>)</mo> <mo>÷</mo> <mi>b</mi> <mo>=</mo> <mrow> <mrow> <mo>{</mo> <mtable> <mtr> <mtd> <mi>s</mi> </mtd> <mtd> <mrow> <mstyle> <mtext>if </mtext> </mstyle> </mrow> <mi>a</mi> <mo>=</mo> <mi>b</mi> </mtd> </mtr> <mtr> <mtd> <mo>(</mo> <mi>s</mi> <mo>÷</mo> <mi>b</mi> <mo>)</mo> <mi>a</mi> </mtd> <mtd> <mrow> <mstyle> <mtext>if </mtext> </mstyle> </mrow> <mi>a</mi> <mo>≠</mo> <mi>b</mi> </mtd> </mtr> </mtable> <mo></mo> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle (sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a eq b\end{cases}}}</annotation> </semantics> </math></span><img src=

La chaîne vide est toujours annulable :

{\displaystyle \varepsilon \div a=\varepsilon <semantics> <mrow> <mstyle> <mi>ε</mi> <mo>÷</mo> <mi>a</mi> <mo>=</mo> <mi>ε</mi> </mstyle> </mrow> <annotation>{\displaystyle \varepsilon \div a=\varepsilon }</annotation> </semantics> </math></span><img src=

De toute évidence, l'annulation à droite et la projection commutent :

{\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a) <semantics> <mrow> <mstyle> <msub> <mi>π</mi> <mrow> <mi>Σ</mi> </mrow> </msub> <mo>(</mo> <mi>s</mi> <mo>)</mo> <mo>÷</mo> <mi>a</mi> <mo>=</mo> <msub> <mi>π</mi> <mrow> <mi>Σ</mi> </mrow> </msub> <mo>(</mo> <mi>s</mi> <mo>÷</mo> <mi>a</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)}</annotation> </semantics> </math></span><img src=

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)^{*}\ <semantics> <mrow> <mstyle> <msub> <mi>Pref</mi> <mrow> <mi>L</mi> </mrow> </msub> <mo>⁡</mo> <mo>(</mo> <mi>s</mi> <mo>)</mo> <mo>=</mo> <mo>{</mo> <mi>t</mi> <mtext> </mtext> <mo>|</mo> <mtext> </mtext> <mi>s</mi> <mo>=</mo> <mi>t</mi> <mi>u</mi> <mrow> <mstyle> <mtext> for </mtext> </mstyle> </mrow> <mi>t</mi> <mo>,</mo> <mi>u</mi> <mo>∈</mo> <mi>Alph</mi> <mo>⁡</mo> <mo>(</mo> <mi>L</mi> <msup> <mo>)</mo> <mrow> <mo>∗</mo> </mrow> </msup> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \operatorname {Pref} _{L}(s)=\{t\ \vert \ s=tu{\mbox{ for }}t,u\in \operatorname {Alph} (L)^{*}\}}</annotation> </semantics> </math></span><img src=

où . ${\displaystyle s\in L <semantics> <mrow> <mstyle> <mi>s</mi> <mo>∈</mo> <mi>L</mi> </mstyle> </mrow> <annotation>{\displaystyle s\in L}</annotation> </semantics> </math><img src=$

La fermeture du préfixe 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)^{*} ight\ <semantics> <mrow> <mstyle> <mi>Pref</mi> <mo>⁡</mo> <mo>(</mo> <mi>L</mi> <mo>)</mo> <mo>=</mo> <munder> <mo>⋃</mo> <mrow> <mi>s</mi> <mo>∈</mo> <mi>L</mi> </mrow> </munder> <msub> <mi>Pref</mi> <mrow> <mi>L</mi> </mrow> </msub> <mo>⁡</mo> <mo>(</mo> <mi>s</mi> <mo>)</mo> <mo>=</mo> <mrow> <mo>{</mo> <mrow> <mi>t</mi> <mtext> </mtext> <mo>|</mo> <mtext> </mtext> <mi>s</mi> <mo>=</mo> <mi>t</mi> <mi>u</mi> <mo>;</mo> <mi>s</mi> <mo>∈</mo> <mi>L</mi> <mo>;</mo> <mi>t</mi> <mo>,</mo> <mi>u</mi> <mo>∈</mo> <mi>Alph</mi> <mo>⁡</mo> <mo>(</mo> <mi>L</mi> <msup> <mo>)</mo> <mrow> <mo>∗</mo> </mrow> </msup> </mrow> <mo>}</mo> </mrow> </mstyle> </mrow> <annotation>{\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)^{*} ight\}}</annotation> </semantics> </math></span><img src=

Exemple:
${\displaystyle L=\left\{abc ight\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc ight\ <semantics> <mrow> <mstyle> <mi>L</mi> <mo>=</mo> <mrow> <mo>{</mo> <mrow> <mi>a</mi> <mi>b</mi> <mi>c</mi> </mrow> <mo>}</mo> </mrow> <mrow> <mstyle> <mtext> then </mtext> </mstyle> </mrow> <mi>Pref</mi> <mo>⁡</mo> <mo>(</mo> <mi>L</mi> <mo>)</mo> <mo>=</mo> <mrow> <mo>{</mo> <mrow> <mi>ε</mi> <mo>,</mo> <mi>a</mi> <mo>,</mo> <mi>a</mi> <mi>b</mi> <mo>,</mo> <mi>a</mi> <mi>b</mi> <mi>c</mi> </mrow> <mo>}</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle L=\left\{abc ight\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc ight\}}</annotation> </semantics> </math><img src=$

Une langue est dite préfixée fermée si . ${\displaystyle \operatorname {Pref} (L)=L <semantics> <mrow> <mstyle> <mi>Pref</mi> <mo>⁡</mo> <mo>(</mo> <mi>L</mi> <mo>)</mo> <mo>=</mo> <mi>L</mi> </mstyle> </mrow> <annotation>{\displaystyle \operatorname {Pref} (L)=L}</annotation> </semantics> </math><img src=$

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

{\displaystyle \operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L) <semantics> <mrow> <mstyle> <mi>Pref</mi> <mo>⁡</mo> <mo>(</mo> <mi>Pref</mi> <mo>⁡</mo> <mo>(</mo> <mi>L</mi> <mo>)</mo> <mo>)</mo> <mo>=</mo> <mi>Pref</mi> <mo>⁡</mo> <mo>(</mo> <mi>L</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle \operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)}</annotation> </semantics> </math></span><img src=

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 <semantics> <mrow> <mstyle> <mo>⊑</mo> </mstyle> </mrow> <annotation>{\displaystyle \sqsubseteq }</annotation> </semantics> </math><img src=$ ${\displaystyle s\sqsubseteq t <semantics> <mrow> <mstyle> <mi>s</mi> <mo>⊑</mo> <mi>t</mi> </mstyle> </mrow> <annotation>{\displaystyle s\sqsubseteq t}</annotation> </semantics> </math><img src=$ ${\displaystyle s\in \operatorname {Pref} _{L}(t) <semantics> <mrow> <mstyle> <mi>s</mi> <mo>∈</mo> <msub> <mi>Pref</mi> <mrow> <mi>L</mi> </mrow> </msub> <mo>⁡</mo> <mo>(</mo> <mi>t</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle s\in \operatorname {Pref} _{L}(t)}</annotation> </semantics> </math><img src=$