String-Operationen

In der Informatik , insbesondere in der Theorie formaler Sprachen , werden häufig verschiedene Stringfunktionen verwendet . Die verwendete Notation unterscheidet sich jedoch von der in der Programmierung üblichen , und einige in der Theorie gebräuchliche Funktionen finden in der Praxis selten Anwendung. Dieser Artikel definiert einige dieser grundlegenden Begriffe.

Eine Zeichenkette ist eine endliche Folge von Zeichen. Die leere Zeichenkette wird mit 0 bezeichnet . Die Verkettung zweier Zeichenketten und wird mit 1/2 oder kürzer mit 1/2 bezeichnet . Die Verkettung mit der leeren Zeichenkette ändert nichts: 1/2 = 1/2 . Die Verkettung von Zeichenketten ist assoziativ : 1/2 = 1/2. ${\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}$

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

Eine Sprache ist eine endliche oder unendliche Menge von Zeichenketten. Neben den üblichen Mengenoperationen wie Vereinigung, Schnittmenge usw. kann die Verkettung auf Sprachen angewendet werden: Sind sowohl A als auch B Sprachen, so ist ihre Verkettung definiert als die Menge der Verkettungen beliebiger Zeichenketten aus A und B , formal ℝ = Aℝ . Der Verkettungspunkt wird der Kürze halber oft weggelassen. ${\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 }$

Die Sprache, die nur aus dem leeren String besteht, ist von der leeren Sprache zu unterscheiden . Die Verkettung einer beliebigen Sprache mit ersterer ergibt keine Änderung: , während die Verkettung mit letzterer immer die leere Sprache ergibt: . Die Verkettung von Sprachen ist assoziativ: . ${\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}$

Beispielsweise erhält man durch Abkürzen von die Menge aller dreistelligen Dezimalzahlen als . Die Menge aller Dezimalzahlen beliebiger Länge ist ein Beispiel für eine unendliche Sprache. ${\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}$

Das Alphabet einer Zeichenkette ist die Menge aller Zeichen, die in dieser Zeichenkette vorkommen. Wenn s eine Zeichenkette ist, wird ihr Alphabet mit bezeichnet.

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

Das Alphabet einer Sprache ist die Menge aller Zeichen, die in jeder beliebigen Zeichenkette vorkommen , formal: . ${\displaystyle S}$${\displaystyle S}$${\displaystyle \operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)}$

Zum Beispiel ist die Menge das Alphabet der Zeichenkette , und das Obige ist das Alphabet der oben genannten Sprache sowie der Sprache aller Dezimalzahlen. ${\displaystyle \{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}}$${\displaystyle \langle cacao\rangle }$${\displaystyle D}$${\displaystyle D\cdot D\cdot D}$

Sei L eine Sprache und Σ ihr Alphabet. Eine Zeichenkettensubstitution oder kurz Substitution ist eine Abbildung f , die Zeichen aus Σ auf Sprachen (möglicherweise mit einem anderen Alphabet) abbildet. So gilt beispielsweise für ein gegebenes Zeichen a ∈ Σ: f ( a ) = L _a, wobei L _a ⊆ Δ ^* eine Sprache mit dem Alphabet Δ ist. Diese Abbildung lässt sich auf Zeichenketten erweitern als

f (ε)=ε

für die leere Zeichenkette ε, und

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

für Zeichenketten s ∈ L und Zeichen a ∈ Σ. Zeichenkettenersetzungen können auf ganze Sprachen erweitert werden, wie ^{[ 1 ]}

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

Reguläre Sprachen sind unter Zeichenkettensubstitution abgeschlossen. Das heißt, wenn jedes Zeichen des Alphabets einer regulären Sprache durch ein Zeichen einer anderen regulären Sprache ersetzt wird, ist das Ergebnis immer noch eine reguläre Sprache. ^{[ 2 ]} Analog dazu sind kontextfreie Sprachen unter Zeichenkettensubstitution abgeschlossen. ^{[ 3 ] [ Anmerkung 1 ]}

Ein einfaches Beispiel ist die Umwandlung von f _uc (.) in einen Großbuchstaben, die beispielsweise wie folgt definiert werden kann:

Für die Erweiterung von f _uc auf Zeichenketten haben wir z.B.

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

Für die Erweiterung von f _uc auf Sprachen haben wir z.B.

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

Ein Stringhomomorphismus ( in der formalen Sprachtheorie oft einfach als Homomorphismus bezeichnet ) ist eine Stringsubstitution, bei der jedes Zeichen durch einen einzelnen String ersetzt wird. Das heißt, , wobei ein String ist, für jedes Zeichen . ^{[ Anmerkung 2 ] [ 4 ]}${\displaystyle f(a)=s}$${\displaystyle s}$${\displaystyle a}$

Stringhomomorphismen sind Monoidmorphismen auf dem freien Monoid , die den leeren String und die binäre Operation der Stringverkettung erhalten . Gegeben eine Sprache , heißt die Menge das homomorphe Bild von . Das inverse homomorphe Bild eines Strings ist definiert als ${\displaystyle L}$${\displaystyle f(L)}$${\displaystyle L}$${\displaystyle s}$

${\displaystyle f^{-1}(s)=\{w\mid f(w)=s\}}$

Das inverse homomorphe Bild einer Sprache ist definiert als ${\displaystyle L}$

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

Im Allgemeinen gilt: , obwohl man hat ${\displaystyle f(f^{-1}(L))\neq L}$

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

Und

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

für jede Sprache . ${\displaystyle L}$

Die Klasse der regulären Sprachen ist abgeschlossen unter Homomorphismen und inversen Homomorphismen. ^{[ 5 ]} Ebenso sind die kontextfreien Sprachen abgeschlossen unter Homomorphismen ^{[ Anmerkung 3 ]} und inversen Homomorphismen. ^{[ 6 ]}

Ein Stringhomomorphismus heißt ε-frei (oder e-frei), wenn für alle a im Alphabet gilt : . Einfache Einbuchstaben- Substitutionschiffren sind Beispiele für (ε-freie) Stringhomomorphismen. ${\displaystyle f(a)\neq \varepsilon }$${\displaystyle \Sigma }$

Ein Beispiel für einen Stringhomomorphismus g _uc lässt sich auch durch eine ähnliche Definition wie die obige Substitution erhalten: g _uc (‹a›) = ‹A›, ..., g _uc (‹0›) = ε, wobei g _uc jedoch für Satzzeichen undefiniert ist. Beispiele für inverse homomorphe Bilder sind

• g _uc ⁻¹ ({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, da g _uc (‹sss›) = g _uc (‹sß›) = g _uc (‹ßs›) = ‹SSS›, und
• g _uc ⁻¹ ({ ‹A›, ‹bb› }) = { ‹a› }, da g _uc (‹a›) = ‹A›, während ‹bb› von g _uc nicht erreicht werden kann .

Für die letztgenannte Sprache gilt: g _uc ( g _uc ⁻¹ ({ ‹A›, ‹bb› })) = g _uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }. Der Homomorphismus g _uc ist nicht ε-frei, da er z. B. ‹0› auf ε abbildet.

Ein sehr einfaches Beispiel für einen String-Homomorphismus, bei dem jedes Zeichen genau einem anderen Zeichen zugeordnet wird, ist die Umwandlung eines EBCDIC -kodierten Strings in ASCII .

Wenn s eine Zeichenkette und a ein Alphabet ist, dann ist die Zeichenkettenprojektion von s die Zeichenkette, die entsteht, indem man alle Zeichen entfernt, die nicht in a enthalten sind . Sie wird als s = s⁻¹ geschrieben . Formal ist sie definiert durch das Entfernen von Zeichen von der rechten Seite: ${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle \pi _{\Sigma }(s)\,}$

${\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\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases}}}$

Hier bezeichnet das leere Zeichen . Die Projektion eines Zeichens ist im Wesentlichen dasselbe wie eine Projektion in der relationalen Algebra . ${\displaystyle \varepsilon }$

Die Stringprojektion kann zur Projektion einer Sprache erweitert werden . Gegeben sei eine formale Sprache L , so ist ihre Projektion gegeben durch

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

Der Rechtsquotient eines Zeichens a aus einer Zeichenkette s ist die Kürzung des Zeichens a in der Zeichenkette s von rechts. Er wird mit bezeichnet . Falls die Zeichenkette kein a auf der rechten Seite enthält , ist das Ergebnis die leere Zeichenkette.${\displaystyle s/a}$

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

Man kann den Quotienten der leeren Zeichenkette nehmen:

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

Analog dazu kann man, gegeben eine Teilmenge eines Monoids , die Quotiententeilmenge wie folgt definieren: ${\displaystyle S\subset M}$${\displaystyle M}$

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

Linksquotienten können auf ähnliche Weise definiert werden, wobei die Operationen links von einer Zeichenkette stattfinden.

_Hopcroft und Ullman (1979) definieren den Quotienten L₁ / _L₂ der Sprachen L₁ und _L₂ über demselben Alphabet als _L₁ / L₂ = { s | ∃ t ∈ L₂ _. st ∈ L₁ _} . ^{[ 7 ]} _{Dies ist} keine Verallgemeinerung der obigen Definition, da die Definition von Hopcroft und Ullman für eine Zeichenkette s und verschiedene Zeichen a , b impliziert , _dass …ergibt {}, anstatt { ε }.

Der linke Quotient (definiert analog zu Hopcroft und Ullman 1979) einer einelementigen Sprache L₁ und einer beliebigen Sprache L₂ wird als Brzozowski-Ableitung bezeichnet ; wenn L₂ durch einen regulären Ausdruck dargestellt wird , kann auch der linke Quotient _{durch einen regulären Ausdruck dargestellt werden.} ^{[ 8 ]}

Der rechte Quotient einer Teilmenge eines Monoids definiert eine Äquivalenzrelation , die als rechte syntaktische Relation von S bezeichnet wird . Sie ist gegeben durch ${\displaystyle S\subset M}$${\displaystyle M}$

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

Die Relation ist offensichtlich von endlichem Index (hat eine endliche Anzahl von Äquivalenzklassen) genau dann, wenn die Familie der Rechtsquotienten endlich ist; das heißt, wenn

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

ist endlich. Falls M das Monoid der Wörter über einem Alphabet ist, dann ist S eine reguläre Sprache , d. h. eine Sprache, die von einem endlichen Automaten erkannt werden kann. Dies wird im Artikel über syntaktische Monoide ausführlicher behandelt .

Die Rechtskürzung eines Zeichens a aus einer Zeichenkette s ist das Entfernen des ersten Vorkommens des Zeichens a in der Zeichenkette s , beginnend von rechts. Sie wird mit bezeichnet und rekursiv definiert als ${\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{cases}}}$

Der leere String kann immer abgebrochen werden:

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

Offensichtlich handelt es sich um eine Pendelstrecke zwischen Rechtsaufhebung und Projektion :

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

Die Präfixe einer Zeichenkette sind die Menge aller Präfixe einer Zeichenkette in Bezug auf eine gegebene Sprache:

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

Wo . ${\displaystyle s\in L}$

Der Präfixabschluss einer Sprache ist

${\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\}}$

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

Eine Sprache heißt präfixabgeschlossen, wenn . ${\displaystyle \operatorname {Pref} (L)=L}$

Der Präfix-Abschlussoperator ist idempotent :

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

Die Präfixrelation ist eine binäre Relation, die genau dann gilt, wenn . Diese Relation ist ein Spezialfall einer Präfixreihenfolge . ${\displaystyle \sqsubseteq }$${\displaystyle s\sqsubseteq t}$${\displaystyle s\in \operatorname {Pref} _{L}(t)}$

• Vergleich von Programmiersprachen (Zeichenkettenfunktionen)
• Levis Lemma
• String (Informatik) – Definition und Implementierung grundlegender Operationen auf Zeichenketten

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Einführung in die Automatentheorie, Sprachen und Berechenbarkeit . Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl  0426.68001 .(Siehe Kapitel 3.)