www.wikidata.de-de.nina.az

Wort theoretische Informatik In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabe

Wort (theoretische Informatik)

In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets. Im Gegensatz zur natürlichsprachlichen Bedeutung von Wörtern, die stets eine eigenständige Bedeutung haben, bezeichnet der Ausdruck Wort in der theoretischen Informatik lediglich eine Zeichenkette und nicht deren mögliche Bedeutung.

Wörter oder Worte sind die Elemente einer formalen Sprache. Sie sind deshalb wichtig für mathematische Modellierungen, für die Theorie der Programmiersprachen, für die Berechenbarkeitstheorie und andere Gebiete der theoretischen Informatik.

Definition Bearbeiten

Es sei ein gegebenes Alphabet und eine natürliche Zahl aus , der Menge der natürlichen Zahlen einschließlich der Null (). Ein Wort der Länge ist eine endliche Folge mit für alle .

Die Länge eines Wortes wird als notiert; die Zahl, wie oft das Zeichen im Wort vorkommt, mit . Ein besonderes Wort ist das leere Wort, das aus keinem Symbol besteht (die Länge 0 besitzt) und meist mit dem griechischen Buchstaben (Epsilon) dargestellt wird (auch findet man gelegentlich). Die Menge aller Wörter, die man aus einem Alphabet bilden kann, ist die Kleenesche und positive Hülle über diesem Alphabet. Diese ist die disjunkte Vereinigung

Die nichtleeren Wörter sind dann entsprechend die ‚positive Hülle’

Zur Angabe eines Wortes wird oft die vereinfachte Schreibweise benutzt, was jedoch nur möglich ist, wenn das verwendete Alphabet eine eindeutige Zuordnung der benutzten Symbole zulässt. So kann diese Kurzschreibweise beim Alphabet nicht angewendet werden, da hier zum Beispiel aus der Schreibweise nicht eindeutig hervorgeht, ob das Wort , oder gemeint ist.

Wörter der Länge können wie folgt aufgefasst werden:

  • als endliche Folgen (Sequenz) – da Tupel als Folgen mit endlicher Länge aufgefasst werden können
  • als Elemente des -fachen kartesischen Produktes – da Tupel auch so aufgefasst werden können

Beispiele Bearbeiten

Es sei das Alphabet der lateinischen Buchstaben und . Dann sind die Wörter und Beispiele für Wörter über und ist ein Wort über . Man erkennt, dass und ist.

Operationen auf Wörtern Bearbeiten

Konkatenation Bearbeiten

Die Konkatenation oder Verkettung ist eine Verknüpfung zweier Wörter zu einem neuen Wort, das durch Aneinanderhängen der beiden Symbolfolgen entsteht. Die Konkatenation der beiden Wörter und über einem Alphabet wird mit oder angegeben und ist definiert durch:

Dabei ist nach der Definition des Wortes und mit und für alle und . Nach der obigen Definition ist ein Präfix und ein Suffix des durch die Konkatenation entstandenen Wortes . Die Länge eines konkatenierten Wortes entspricht dabei der Summe der Längen der einzelnen (Teil-)Wörter. So gilt für jedes Wort und :

und für die absolute Häufigkeit eines Zeichens :

Das neutrale Element der Konkatenation ist das leere Wort, da für jedes beliebige Wort gilt, dass:

Da außerdem die Konkatenation assoziativ ist, bildet das Tripel aus der Menge aller Wörter über einem beliebigen Alphabet , der Verknüpfung der Konkatenation und dem leeren Wort als neutralem Element ein Monoid. Die Assoziativität bedeutet, dass ohne weiteres Klammern weggelassen werden können:

Demgegenüber ist die Konkatenation nicht kommutativ, d. h. nicht für alle Wörter und gilt, dass ist. So ist zum Beispiel:

Potenz Bearbeiten

Die -te Potenz eines Wortes ist definiert als die -fache Konkatenation dieses Wortes mit sich selbst. Die Definition der Potenz wird meist rekursiv angegeben:

So sind zum Beispiel:

Nach der Definition der Konkatenation ist die Länge der -ten Potenz eines beliebigen Wortes gleich dem Produkt aus und der Länge von :

und für die absolute Häufigkeit eines jeden Zeichens :

Spiegelung Bearbeiten

Die Spiegelung oder das Reverse eines Wortes ergibt sich, wenn man rückwärts schreibt. Wenn also ist, so ist die endliche Folge mit und für alle . Die Länge eines Wortes ist also gleich der Länge seiner Spiegelung:

So gilt zum Beispiel für die folgenden Wörter:

Das Reverse eines Wortes lässt sich außerdem mit Hilfe der strukturellen Induktion über dem Aufbau des betreffenden Wortes definieren. Dazu definiert man im Induktionsanfang das Reverse des leeren Wortes als das leere Wort. Im Induktionsschritt definiert man das Reverse eines aus einem Teilwort und einem Symbol zusammengesetzten Wortes als die Konkatenation des Symbols mit dem Reversen des Teilwortes:

Induktionsanfang:

Induktionsschritt:

So lässt sich schrittweise das Reverse eines Wortes herleiten:

Ein Wort wie , das identisch mit seiner Spiegelung ist, wird Palindrom genannt. Mathematisch werden diese spiegelsymmetrischen Worte als die Fixpunkte der Spiegelung R angesehen.

Präfix, Infix und Suffix Bearbeiten

Infix Bearbeiten

Ein Infix ist eine Hinzufügung innerhalb eines Wortes. Jede endliche Teilfolge von aufeinander folgenden Symbolen eines Wortes wird Infix, Teilwort oder Faktor des Wortes genannt. Ein Infix eines gegebenen Wortes ist demnach jedes Wort , für das es (mindestens) ein gibt, für das gilt, dass zum einen und zum anderen für jedes ist. Demnach ist ein Wort genau dann Infix eines Wortes , wenn gilt, dass es mindestens ein Wort und ein Wort aus der Kleeneschen Hülle über dem Alphabet von gibt, so dass ist:

So ist das Wort mit ein Infix der Wörter , und , nicht aber der Wörter , beziehungsweise des leeren Wortes . In vielen Computersprachen ist für Infix die englische Bezeichnung substring gebräuchlich.

Speziell ist das leere Wort ein Infix jedes beliebigen Wortes, und jedes Wort ist ein Infix von sich selbst. Ein Infix eines beliebigen Wortes, das nicht identisch mit diesem ist, wird echtes Infix genannt.

Präfix Bearbeiten

Ein Präfix ist eine Hinzufügung am Anfang eines Wortes. Ein Präfix eines Wortes ist demnach jedes Infix , für das gilt, dass und für jedes ist. Demnach ist genau dann Präfix des Wortes , wenn es mindestens ein aus der Kleeneschen Hülle über dem Alphabet, aus dem erzeugt wurde, gibt, so dass ist:

Auch für Präfixe gilt, dass jedes Wort ein Präfix von sich selbst und das leere Wort ein Präfix jedes beliebigen Wortes ist. Ein Präfix eines Wortes, das nicht identisch mit ihm ist, wird echtes Präfix genannt.

Beispiel Bearbeiten

Sei , so lauten die echten Präfixe für :

  • .

Suffix Bearbeiten

Ein Suffix, auch Postfix genannt, ist eine Hinzufügung am Ende eines Wortes. Ein Suffix eines Wortes ist nach der Definition des Infixes jedes Teilwort , für das gilt, dass es ein gibt, für das zum einen und zum anderen für jedes ist. Demnach ist ein Wort genau dann Suffix eines Wortes mit , wenn es mindestens ein gibt, so dass ist:

Wie für Präfixe und Infixe gilt auch für Suffixe, dass das leere Wort ein Suffix jedes beliebigen Wortes und ein beliebiges Wort stets auch ein Suffix von sich selbst ist. Ein Suffix eines Wortes, das nicht identisch mit ihm ist, wird echtes Suffix genannt.

Beispiel Bearbeiten

Sei , so lauten die echten Suffixe für :

  • .

Literatur Bearbeiten

  • John E. Hopcroft, Jeffry D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 3. korrigierte Auflage. Addison-Wesley, Bonn u. a. 1994, ISBN 3-89319-744-3 (Internationale Computer-Bibliothek).
  • Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung. 2. erweiterte Auflage. Springer-Verlag, Berlin u. a. 2002, ISBN 3-540-42624-8, S. 27–28 (Springer-Lehrbuch).
  • Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs theoretische Informatik. Eine anwendungsbezogene Einführung - für Studierende in allen Informatik-Studiengängen. 4. verbesserte und erweiterte Auflage. Vieweg, Wiesbaden 2006, ISBN 3-8348-0153-4, S. 15 (online).
  • M. Lothaire: Combinatorics on Words. Cambridge University Press, 1997, ISBN 978-0-511-56609-7, S. 1 ff., doi:10.1017/CBO9780511566097.

Anmerkungen und Einzelnachweise Bearbeiten

  1. Gebräuchlich sind beide Pluralformen, vgl. z. B. dtv-Atlas zur Mathematik, Bd. I, ISBN 3-423-03007-0, S. 245 versus Bauer, Goos: Informatik. Bd. I, ISBN 3-540-06332-3, S. 28.
  2. Klaus Reinhardt: Prioritätszählerautomaten und die Synchronisation von Halbspursprachen, Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994 (PDF; 509 KB)
  3. Dabei ist .
  4. Yuri L. Ershov, Eugenii A. Palyutin: Mathematical Logic. Translated from the Russian by Vladimir Shokurov. Revised from the 1979 Russian edition. Mir Publishers, Moskau 1984, S. 16 (mirtitles.org).
  5. Definition von Tupel und seine Synonyme: Encyclopedia of Mathematics: Tuple
  6. Die Spiegelung eines Wortes der Länge n ist eine spezielle selbstinverse Permutation Die Spiegelung beliebig langer Wörter ist dann die Vereinigung

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets Im Gegensatz zur naturlichsprachlichen Bedeutung von Wortern die stets eine eigenstandige Bedeutung haben bezeichnet der Ausdruck Wort in der theoretischen Informatik lediglich eine Zeichenkette und nicht deren mogliche Bedeutung Worter oder Worte 1 sind die Elemente einer formalen Sprache Sie sind deshalb wichtig fur mathematische Modellierungen fur die Theorie der Programmiersprachen fur die Berechenbarkeitstheorie und andere Gebiete der theoretischen Informatik Inhaltsverzeichnis 1 Definition 2 Beispiele 3 Operationen auf Wortern 3 1 Konkatenation 3 2 Potenz 3 3 Spiegelung 4 Prafix Infix und Suffix 4 1 Infix 4 2 Prafix 4 2 1 Beispiel 4 3 Suffix 4 3 1 Beispiel 5 Literatur 6 Anmerkungen und Einzelnachweise 7 WeblinksDefinition BearbeitenEs sei S displaystyle Sigma nbsp ein gegebenes Alphabet und n displaystyle n nbsp eine naturliche Zahl aus N 0 displaystyle mathbb N 0 nbsp der Menge der naturlichen Zahlen einschliesslich der Null N 0 0 1 2 displaystyle mathbb N 0 0 1 2 ldots nbsp Ein Wort w displaystyle w nbsp der Lange n displaystyle n nbsp ist eine endliche Folge x 1 x 2 x 3 x n displaystyle x 1 x 2 x 3 ldots x n nbsp mit x i S displaystyle x i in Sigma nbsp fur alle i 1 n displaystyle i in 1 ldots n nbsp Die Lange n displaystyle n nbsp eines Wortes w displaystyle w nbsp wird als w displaystyle w nbsp notiert die Zahl wie oft das Zeichen x displaystyle x nbsp im Wort w displaystyle w nbsp vorkommt mit w x displaystyle w x nbsp 2 3 Ein besonderes Wort ist das leere Wort das aus keinem Symbol besteht die Lange 0 besitzt und meist mit dem griechischen Buchstaben e displaystyle varepsilon nbsp Epsilon dargestellt wird auch L displaystyle Lambda nbsp findet man gelegentlich 4 Die Menge aller Worter die man aus einem Alphabet S displaystyle Sigma nbsp bilden kann ist die Kleenesche und positive Hulle uber diesem Alphabet Diese ist die disjunkte Vereinigung S n N 0 S n displaystyle Sigma bigcup n in mathbb N cup 0 Sigma n nbsp Die nichtleeren Worter sind dann entsprechend die positive Hulle S S e n N S n displaystyle Sigma Sigma setminus varepsilon bigcup n in mathbb N Sigma n nbsp Zur Angabe eines Wortes wird oft die vereinfachte Schreibweise w x 1 x 2 x 3 x n displaystyle w x 1 x 2 x 3 ldots x n nbsp benutzt was jedoch nur moglich ist wenn das verwendete Alphabet eine eindeutige Zuordnung der benutzten Symbole zulasst So kann diese Kurzschreibweise beim Alphabet S a a a displaystyle Sigma a aa nbsp nicht angewendet werden da hier zum Beispiel aus der Schreibweise w a a a displaystyle w aaa nbsp nicht eindeutig hervorgeht ob das Wort a a a displaystyle a aa nbsp a a a displaystyle aa a nbsp oder a a a displaystyle a a a nbsp gemeint ist Worter der Lange n displaystyle n nbsp konnen wie folgt aufgefasst werden 5 als endliche Folgen Sequenz da Tupel als Folgen mit endlicher Lange n displaystyle n nbsp aufgefasst werden konnen als Elemente des n displaystyle n nbsp fachen kartesischen Produktes da Tupel auch so aufgefasst werden konnenBeispiele BearbeitenEs sei S 1 displaystyle Sigma 1 nbsp das Alphabet der lateinischen Buchstaben und S 2 displaystyle Sigma 2 lbrace diamondsuit heartsuit spadesuit clubsuit rbrace nbsp Dann sind die Worter w 1 h a u s displaystyle w 1 haus nbsp und w 2 x y z z y displaystyle w 2 xyzzy nbsp Beispiele fur Worter uber S 1 displaystyle Sigma 1 nbsp und w 3 displaystyle w 3 heartsuit clubsuit clubsuit heartsuit spadesuit nbsp ist ein Wort uber S 2 displaystyle Sigma 2 nbsp Man erkennt dass w 1 4 displaystyle w 1 4 nbsp und w 2 w 3 5 displaystyle w 2 w 3 5 nbsp ist Operationen auf Wortern BearbeitenKonkatenation Bearbeiten Die Konkatenation oder Verkettung ist eine Verknupfung zweier Worter zu einem neuen Wort das durch Aneinanderhangen der beiden Symbolfolgen entsteht Die Konkatenation der beiden Worter x displaystyle x nbsp und y displaystyle y nbsp uber einem Alphabet S displaystyle Sigma nbsp wird mit x y displaystyle xy nbsp oder x y displaystyle x circ y nbsp angegeben und ist definiert durch x y x y x 1 x 2 x 3 x n y 1 y 2 y 3 y k displaystyle xy x circ y x 1 x 2 x 3 ldots x n y 1 y 2 y 3 ldots y k nbsp Dabei ist nach der Definition des Wortes x x 1 x 2 x 3 x n displaystyle x x 1 x 2 x 3 ldots x n nbsp und y y 1 y 2 y 3 y k displaystyle y y 1 y 2 y 3 ldots y k nbsp mit n k N 0 displaystyle n k in mathbb N 0 nbsp und x i y j S displaystyle x i y j in Sigma nbsp fur alle i 1 n displaystyle i in 1 ldots n nbsp und j 1 k displaystyle j in 1 ldots k nbsp Nach der obigen Definition ist x displaystyle x nbsp ein Prafix und y displaystyle y nbsp ein Suffix des durch die Konkatenation entstandenen Wortes x y displaystyle x circ y nbsp Die Lange eines konkatenierten Wortes entspricht dabei der Summe der Langen der einzelnen Teil Worter So gilt fur jedes Wort u displaystyle u nbsp und v displaystyle v nbsp u v u v displaystyle u circ v u v nbsp und fur die absolute Haufigkeit eines Zeichens x displaystyle x nbsp u v x u x v x displaystyle u circ v x u x v x nbsp Das neutrale Element der Konkatenation ist das leere Wort da fur jedes beliebige Wort w displaystyle w nbsp gilt dass w e e w w displaystyle w circ varepsilon varepsilon circ w w nbsp Da ausserdem die Konkatenation assoziativ ist bildet das Tripel S e displaystyle Sigma circ varepsilon nbsp aus der Menge aller Worter uber einem beliebigen Alphabet S displaystyle Sigma nbsp der Verknupfung der Konkatenation und dem leeren Wort als neutralem Element ein Monoid Die Assoziativitat bedeutet dass ohne weiteres Klammern weggelassen werden konnen h a u s x y z z y h a u s x y z z y h a u s x y z z y displaystyle haus circ heartsuit clubsuit clubsuit heartsuit spadesuit circ xyzzy haus circ heartsuit clubsuit clubsuit heartsuit spadesuit circ xyzzy haus heartsuit clubsuit clubsuit heartsuit spadesuit xyzzy nbsp Demgegenuber ist die Konkatenation nicht kommutativ d h nicht fur alle Worter u displaystyle u nbsp und v displaystyle v nbsp gilt dass u v v u displaystyle u circ v v circ u nbsp ist So ist zum Beispiel h a u s h a u s h a u s h a u s displaystyle haus circ heartsuit clubsuit clubsuit heartsuit spadesuit haus heartsuit clubsuit clubsuit heartsuit spadesuit not heartsuit clubsuit clubsuit heartsuit spadesuit haus heartsuit clubsuit clubsuit heartsuit spadesuit circ haus nbsp Potenz Bearbeiten Die n displaystyle n nbsp te Potenz w n displaystyle w n nbsp eines Wortes w displaystyle w nbsp ist definiert als die n 1 displaystyle n 1 nbsp fache Konkatenation dieses Wortes mit sich selbst Die Definition der Potenz wird meist rekursiv angegeben w 0 e displaystyle w 0 varepsilon nbsp w n 1 w n w displaystyle w n 1 w n circ w nbsp fur n N 0 displaystyle n in mathbb N 0 nbsp So sind zum Beispiel x y z z y 0 e displaystyle xyzzy 0 varepsilon nbsp 1 0 e displaystyle heartsuit clubsuit clubsuit heartsuit spadesuit 1 heartsuit clubsuit clubsuit heartsuit spadesuit 0 circ heartsuit clubsuit clubsuit heartsuit spadesuit varepsilon circ heartsuit clubsuit clubsuit heartsuit spadesuit heartsuit clubsuit clubsuit heartsuit spadesuit nbsp h a u s 3 h a u s 2 h a u s h a u s 1 h a u s h a u s e h a u s h a u s h a u s h a u s h a u s h a u s displaystyle haus 3 haus 2 circ haus haus 1 circ haus circ haus varepsilon circ haus circ haus circ haus haushaushaus nbsp Nach der Definition der Konkatenation ist die Lange der n displaystyle n nbsp ten Potenz eines beliebigen Wortes w displaystyle w nbsp gleich dem Produkt aus n displaystyle n nbsp und der Lange von w displaystyle w nbsp w n n w displaystyle w n n cdot w nbsp und fur die absolute Haufigkeit eines jeden Zeichens x displaystyle x nbsp w n x n w x displaystyle w n x n cdot w x nbsp Spiegelung Bearbeiten Die Spiegelung oder das Reverse w R displaystyle w R nbsp eines Wortes w displaystyle w nbsp ergibt sich wenn man w displaystyle w nbsp ruckwarts schreibt 6 Wenn also w x 1 x 2 x 3 x n displaystyle w x 1 x 2 x 3 ldots x n nbsp ist so ist w R displaystyle w R nbsp die endliche Folge y 1 y 2 y 3 y k displaystyle y 1 y 2 y 3 ldots y k nbsp mit k n displaystyle k n nbsp und y i x n 1 i displaystyle y i x n 1 i nbsp fur alle i 1 k displaystyle i in 1 ldots k nbsp Die Lange eines Wortes ist also gleich der Lange seiner Spiegelung w R w displaystyle w R w nbsp So gilt zum Beispiel fur die folgenden Worter e R e displaystyle varepsilon R varepsilon nbsp a b b R b b a displaystyle abb R bba nbsp R displaystyle heartsuit clubsuit spadesuit heartsuit R heartsuit spadesuit clubsuit heartsuit nbsp Das Reverse eines Wortes lasst sich ausserdem mit Hilfe der strukturellen Induktion uber dem Aufbau des betreffenden Wortes definieren Dazu definiert man im Induktionsanfang das Reverse des leeren Wortes als das leere Wort Im Induktionsschritt definiert man das Reverse eines aus einem Teilwort und einem Symbol zusammengesetzten Wortes als die Konkatenation des Symbols mit dem Reversen des Teilwortes Induktionsanfang w e w R e R e displaystyle w varepsilon Rightarrow w R varepsilon R varepsilon nbsp Induktionsschritt w v a v S a S w R v a R a v R displaystyle w v circ a land v in Sigma a in Sigma Rightarrow w R v circ a R a circ v R nbsp So lasst sich schrittweise das Reverse eines Wortes herleiten e R e displaystyle varepsilon R varepsilon nbsp a b b R b a b R b b a R b b a e R b b a e b b a displaystyle abb R b circ ab R b circ b circ a R b circ b circ a circ varepsilon R b circ b circ a circ varepsilon bba nbsp R R R R displaystyle heartsuit clubsuit spadesuit heartsuit R heartsuit circ heartsuit clubsuit spadesuit R heartsuit circ spadesuit circ heartsuit clubsuit R heartsuit circ spadesuit circ clubsuit circ heartsuit R heartsuit spadesuit clubsuit heartsuit nbsp Ein Wort wie a b a a b a displaystyle abaaba nbsp das identisch mit seiner Spiegelung ist wird Palindrom genannt Mathematisch werden diese spiegelsymmetrischen Worte als die Fixpunkte der Spiegelung R angesehen Prafix Infix und Suffix BearbeitenInfix Bearbeiten Ein Infix ist eine Hinzufugung innerhalb eines Wortes Jede endliche Teilfolge von aufeinander folgenden Symbolen eines Wortes w displaystyle w nbsp wird Infix Teilwort oder Faktor des Wortes w displaystyle w nbsp genannt Ein Infix eines gegebenen Wortes w x 1 x 2 x 3 x n displaystyle w x 1 x 2 x 3 ldots x n nbsp ist demnach jedes Wort w y 1 y 2 y 3 y k displaystyle hat w y 1 y 2 y 3 ldots y k nbsp fur das es mindestens ein i N 0 displaystyle i in mathbb N 0 nbsp gibt fur das gilt dass zum einen k i n displaystyle k i leq n nbsp und zum anderen x j i y j displaystyle x j i y j nbsp fur jedes j 1 k displaystyle j in 1 ldots k nbsp ist Demnach ist ein Wort u displaystyle u nbsp genau dann Infix eines Wortes w displaystyle w nbsp wenn gilt dass es mindestens ein Wort p displaystyle p nbsp und ein Wort s displaystyle s nbsp aus der Kleeneschen Hulle uber dem Alphabet von w displaystyle w nbsp gibt so dass p u s w displaystyle p circ u circ s w nbsp ist u displaystyle u nbsp ist Infix von w p s S p u s w displaystyle w Longleftrightarrow exists p s in Sigma ast p circ u circ s w nbsp So ist das Wort w a b a displaystyle hat w aba nbsp mit w a b displaystyle hat w in lbrace a b rbrace nbsp ein Infix der Worter b a b a a b displaystyle babaab nbsp a b a a b a b b displaystyle abaababb nbsp und a b a displaystyle aba nbsp nicht aber der Worter a b b a displaystyle abba nbsp b a b b a a b b a b displaystyle babbaabbab nbsp beziehungsweise des leeren Wortes e displaystyle varepsilon nbsp In vielen Computersprachen ist fur Infix die englische Bezeichnung substring gebrauchlich Speziell ist das leere Wort ein Infix jedes beliebigen Wortes und jedes Wort ist ein Infix von sich selbst Ein Infix eines beliebigen Wortes das nicht identisch mit diesem ist wird echtes Infix genannt Prafix Bearbeiten Ein Prafix ist eine Hinzufugung am Anfang eines Wortes Ein Prafix eines Wortes w x 1 x 2 x 3 x n displaystyle w x 1 x 2 x 3 ldots x n nbsp ist demnach jedes Infix w y 1 y 2 y 3 y k displaystyle hat w y 1 y 2 y 3 ldots y k nbsp fur das gilt dass k n displaystyle k leq n nbsp und x j y j displaystyle x j y j nbsp fur jedes j 1 k displaystyle j in 1 ldots k nbsp ist Demnach ist u displaystyle u nbsp genau dann Prafix des Wortes w displaystyle w nbsp wenn es mindestens ein s displaystyle s nbsp aus der Kleeneschen Hulle uber dem Alphabet aus dem w displaystyle w nbsp erzeugt wurde gibt so dass u s w displaystyle u circ s w nbsp ist u displaystyle u nbsp ist Prafix von w s S u s w displaystyle w Longleftrightarrow exists s in Sigma ast u circ s w nbsp Auch fur Prafixe gilt dass jedes Wort ein Prafix von sich selbst und das leere Wort ein Prafix jedes beliebigen Wortes ist Ein Prafix eines Wortes das nicht identisch mit ihm ist wird echtes Prafix genannt Beispiel Bearbeiten Sei w a b a a b b displaystyle w abaabb nbsp so lauten die echten Prafixe fur w displaystyle w nbsp e displaystyle varepsilon nbsp a displaystyle a nbsp a b displaystyle ab nbsp a b a displaystyle aba nbsp a b a a displaystyle abaa nbsp a b a a b displaystyle abaab nbsp Suffix Bearbeiten Ein Suffix auch Postfix genannt ist eine Hinzufugung am Ende eines Wortes Ein Suffix eines Wortes w x 1 x 2 x 3 x n displaystyle w x 1 x 2 x 3 ldots x n nbsp ist nach der Definition des Infixes jedes Teilwort w y 1 y 2 y 3 y k displaystyle hat w y 1 y 2 y 3 ldots y k nbsp fur das gilt dass es ein i N 0 displaystyle i in mathbb N 0 nbsp gibt fur das zum einen k i n displaystyle k i n nbsp und zum anderen x j i y j displaystyle x j i y j nbsp fur jedes j 1 k displaystyle j in 1 ldots k nbsp ist Demnach ist ein Wort u displaystyle u nbsp genau dann Suffix eines Wortes w displaystyle w nbsp mit w S displaystyle w in Sigma ast nbsp wenn es mindestens ein p S displaystyle p in Sigma ast nbsp gibt so dass p u w displaystyle p circ u w nbsp ist u displaystyle u nbsp ist Suffix von w p S p u w displaystyle w Longleftrightarrow exists p in Sigma ast p circ u w nbsp Wie fur Prafixe und Infixe gilt auch fur Suffixe dass das leere Wort ein Suffix jedes beliebigen Wortes und ein beliebiges Wort stets auch ein Suffix von sich selbst ist Ein Suffix eines Wortes das nicht identisch mit ihm ist wird echtes Suffix genannt Beispiel Bearbeiten Sei w a b a a b b displaystyle w abaabb nbsp so lauten die echten Suffixe fur w displaystyle w nbsp b a a b b displaystyle baabb nbsp a a b b displaystyle aabb nbsp a b b displaystyle abb nbsp b b displaystyle bb nbsp b displaystyle b nbsp e displaystyle varepsilon nbsp Literatur BearbeitenJohn E Hopcroft Jeffry D Ullman Einfuhrung in die Automatentheorie formale Sprachen und Komplexitatstheorie 3 korrigierte Auflage Addison Wesley Bonn u a 1994 ISBN 3 89319 744 3 Internationale Computer Bibliothek Katrin Erk Lutz Priese Theoretische Informatik Eine umfassende Einfuhrung 2 erweiterte Auflage Springer Verlag Berlin u a 2002 ISBN 3 540 42624 8 S 27 28 Springer Lehrbuch Gottfried Vossen Kurt Ulrich Witt Grundkurs theoretische Informatik Eine anwendungsbezogene Einfuhrung fur Studierende in allen Informatik Studiengangen 4 verbesserte und erweiterte Auflage Vieweg Wiesbaden 2006 ISBN 3 8348 0153 4 S 15 online M Lothaire Combinatorics on Words Cambridge University Press 1997 ISBN 978 0 511 56609 7 S 1 ff doi 10 1017 CBO9780511566097 Anmerkungen und Einzelnachweise Bearbeiten Gebrauchlich sind beide Pluralformen vgl z B dtv Atlas zur Mathematik Bd I ISBN 3 423 03007 0 S 245 versus Bauer Goos Informatik Bd I ISBN 3 540 06332 3 S 28 Klaus Reinhardt Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen Fakultat Informatik der Universitat Stuttgart Doktorarbeit 1994 PDF 509 KB Dabei ist w x S w x displaystyle w sum limits x in Sigma w x nbsp Yuri L Ershov Eugenii A Palyutin Mathematical Logic Translated from the Russian by Vladimir Shokurov Revised from the 1979 Russian edition Mir Publishers Moskau 1984 S 16 mirtitles org Definition von Tupel und seine Synonyme Encyclopedia of Mathematics Tuple Die Spiegelung eines Wortes der Lange n ist eine spezielle selbstinverse Permutation s n 1 2 n n n 1 1 displaystyle sigma n begin pmatrix 1 amp 2 amp cdots amp n n amp n 1 amp cdots amp 1 end pmatrix nbsp Die Spiegelung beliebig langer Worter ist dann die Vereinigung R s n n N displaystyle R bigcup sigma n n in mathbb N nbsp Weblinks BearbeitenGrundbegriffe der formalen Sprache Abschnitt Wort Abgerufen von https de wikipedia org w index php title Wort theoretische Informatik amp oldid 232704158