„Wort (Theoretische Informatik)“ – Versionsunterschied
| [ungesichtete Version] | [ungesichtete Version] |
Die Seite wurde neu angelegt: „= Wort (theoretische Informatik) = <p>In der [https://de.wikipedia.org/wiki/Theoretische_Informatik theoretischen Informatik] ist ein '''Wort''' eine endliche [https://de.wikipedia.org/wiki/Folge_(Mathematik) Folge] von [https://de.wikipedia.org/wiki/Symbol Symbolen] eines [https://de.wikipedia.org/wiki/Alphabet_(Informatik) Alphabets]. Im Gegensatz zur [https://de.wikipedia.org/wiki/Nat%C3%BCrliche_Sprache natürlichsprachlichen] Bedeutung von [https://d…“ |
Keine Bearbeitungszusammenfassung |
||
| Zeile 1: | Zeile 1: | ||
[[Wort]] [[Theoretische Informatik|theoretische Informatik]] | |||
= Wort (theoretische Informatik) = | = Wort (theoretische Informatik) = | ||
<p>In der [https://de.wikipedia.org/wiki/Theoretische_Informatik theoretischen Informatik] ist ein '''Wort''' eine endliche [https://de.wikipedia.org/wiki/Folge_(Mathematik) Folge] von [https://de.wikipedia.org/wiki/Symbol Symbolen] eines [https://de.wikipedia.org/wiki/Alphabet_(Informatik) Alphabets]. Im Gegensatz zur [https://de.wikipedia.org/wiki/Nat%C3%BCrliche_Sprache natürlichsprachlichen] Bedeutung von [https://de.wikipedia.org/wiki/Wort Wörtern], die stets eine eigenständige Bedeutung haben, bezeichnet der Ausdruck ''Wort'' in der theoretischen Informatik lediglich eine [https://de.wikipedia.org/wiki/Zeichenkette Zeichenkette] und nicht deren mögliche Bedeutung.</p> | <p>In der [https://de.wikipedia.org/wiki/Theoretische_Informatik theoretischen Informatik] ist ein '''Wort''' eine endliche [https://de.wikipedia.org/wiki/Folge_(Mathematik) Folge] von [https://de.wikipedia.org/wiki/Symbol Symbolen] eines [https://de.wikipedia.org/wiki/Alphabet_(Informatik) Alphabets]. Im Gegensatz zur [https://de.wikipedia.org/wiki/Nat%C3%BCrliche_Sprache natürlichsprachlichen] Bedeutung von [https://de.wikipedia.org/wiki/Wort Wörtern], die stets eine eigenständige Bedeutung haben, bezeichnet der Ausdruck ''Wort'' in der theoretischen Informatik lediglich eine [https://de.wikipedia.org/wiki/Zeichenkette Zeichenkette] und nicht deren mögliche Bedeutung.</p> | ||
| Zeile 4: | Zeile 6: | ||
== <span id="Beschreibung">Beschreibung</span> == | == <span id="Beschreibung">Beschreibung</span> == | ||
<p>Mit einer formalen Grammatik lassen sich ausgehend von einem Startsymbol | <p>Mit einer formalen Grammatik lassen sich ausgehend von einem Startsymbol {{Flzn.S.Strt.}} (auch ''Startvariable'' genannt) [[Produktionsregel]]<nowiki/>n aus einer Regelmenge {{Flzn.P.Prd.Rgl.Mng.}} anwenden, die aus dem Startsymbol neue Zeichenfolgen ([https://de.wikipedia.org/wiki/Wort_(Theoretische_Informatik) Wörter]) erzeugen, welche wiederum weiter ersetzt werden können. Diesen Vorgang nennt man auch [https://de.wikipedia.org/wiki/Ableitung_(Informatik) Ableitung].</p> | ||
<p>Das Vokabular ''V'' einer Grammatik, bestehend aus der [https://de.wikipedia.org/wiki/Disjunkt disjunkten] Vereinigung eines [https://de.wikipedia.org/wiki/Alphabet_(Informatik) Alphabets] ''T'' von [https://de.wikipedia.org/wiki/Terminalsymbol Terminalsymbolen] mit einer Menge von [https://de.wikipedia.org/wiki/Nichtterminalsymbol Nichtterminalsymbolen] ''N'', gibt dabei vor, welche Symbole dafür verwendet werden können. Die Menge der Terminalsymbole definiert, aus welchen Zeichen Wörter bestehen, die nicht weiter abgeleitet werden können. Diese Wörter ergeben zusammengenommen die von der Grammatik beschriebene formale Sprache. Das Startsymbol muss dagegen ein Nichtterminalsymbol sein. Zusätzliche Nichtterminalsymbole erlauben differenziertere Regeln.</p> | <p>Das Vokabular ''V'' einer Grammatik, bestehend aus der [https://de.wikipedia.org/wiki/Disjunkt disjunkten] Vereinigung eines [https://de.wikipedia.org/wiki/Alphabet_(Informatik) Alphabets] ''T'' von [https://de.wikipedia.org/wiki/Terminalsymbol Terminalsymbolen] mit einer Menge von [https://de.wikipedia.org/wiki/Nichtterminalsymbol Nichtterminalsymbolen] ''N'', gibt dabei vor, welche Symbole dafür verwendet werden können. Die Menge der Terminalsymbole definiert, aus welchen Zeichen Wörter bestehen, die nicht weiter abgeleitet werden können. Diese Wörter ergeben zusammengenommen die von der Grammatik beschriebene formale Sprache. Das Startsymbol muss dagegen ein Nichtterminalsymbol sein. Zusätzliche Nichtterminalsymbole erlauben differenziertere Regeln.</p> | ||
<p>Produktionsregeln sind definitionsgemäß [https://de.wikipedia.org/wiki/Geordnetes_Paar geordnete Paare] ( ''α'', ''β'' ), die auch <span class="mwe-math-element">''α →'' ''β''</span> geschrieben werden. Man wendet sie auf eine Zeichenfolge ''w'' an, indem ein Vorkommen der Zeichenfolge <span class="mwe-math-element">''α''</span> in ''w'' durch <span class="mwe-math-element">''β ''</span>ersetzt wird. Auf der linken Seite der Regel muss immer mindestens ein Nichtterminalsymbol stehen. Eine Menge von Regeln mit gleicher linker Seite, also <span class="mwe-math-element">''α →'' ''β''<sub>1</sub>'', ..., α → β''<sub>n</sub></span>, wird abkürzend auch als <span class="mwe-math-element">''α →'' ''β''<sub>1</sub>'', ⎮... ⎮ β<sub>n</sub>''</span> geschrieben.</p> | <p>Produktionsregeln sind definitionsgemäß [https://de.wikipedia.org/wiki/Geordnetes_Paar geordnete Paare] ( ''α'', ''β'' ), die auch <span class="mwe-math-element">''α →'' ''β''</span> geschrieben werden. Man wendet sie auf eine Zeichenfolge ''w'' an, indem ein Vorkommen der Zeichenfolge <span class="mwe-math-element">''α''</span> in ''w'' durch <span class="mwe-math-element">''β ''</span>ersetzt wird. Auf der linken Seite der Regel muss immer mindestens ein Nichtterminalsymbol stehen. Eine Menge von Regeln mit gleicher linker Seite, also <span class="mwe-math-element">''α →'' ''β''<sub>1</sub>'', ..., α → β''<sub>n</sub></span>, wird abkürzend auch als <span class="mwe-math-element">''α →'' ''β''<sub>1</sub>'', ⎮... ⎮ β<sub>n</sub>''</span> geschrieben.</p> | ||
<p>Zum Beispiel kann man mit der Regelmenge ''X'' → ＋ ⎮ － die Zeichenfolge 1''X ''2 entweder zu 1 ＋ 2 oder zu 1 － 2 ableiten.</p> | <p>Zum Beispiel kann man mit der Regelmenge ''X'' → ＋ ⎮ － die Zeichenfolge 1''X ''2 entweder zu 1 ＋ 2 oder zu 1 － 2 ableiten.</p> | ||
<p>Ebenso wie auf eine gegebene Zeichenfolge mehrere Regeln gleichzeitig anwendbar sein können, muss es nicht immer nur eine Stelle in der Zeichenfolge geben, auf die eine Regel passt. Formale Grammatiken schreiben keine Reihenfolge vor. Alle nur aus Terminalsymbolen bestehenden Wörter, die sich aus dem Startsymbol ableiten lassen, zählen zur von der Grammatik beschriebenen Sprache.</p> | <p>Ebenso wie auf eine gegebene Zeichenfolge mehrere Regeln gleichzeitig anwendbar sein können, muss es nicht immer nur eine Stelle in der Zeichenfolge geben, auf die eine Regel passt. Formale Grammatiken schreiben keine Reihenfolge vor. Alle nur aus Terminalsymbolen bestehenden Wörter, die sich aus dem Startsymbol ableiten lassen, zählen zur von der Grammatik beschriebenen Sprache.</p> | ||
Version vom 28. Januar 2024, 07:38 Uhr
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[1] 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.
Beschreibung
Mit einer formalen Grammatik lassen sich ausgehend von einem Startsymbol 𝑆 (auch Startvariable genannt) Produktionsregeln aus einer Regelmenge 𝑃 anwenden, die aus dem Startsymbol neue Zeichenfolgen (Wörter) erzeugen, welche wiederum weiter ersetzt werden können. Diesen Vorgang nennt man auch Ableitung.
Das Vokabular V einer Grammatik, bestehend aus der disjunkten Vereinigung eines Alphabets T von Terminalsymbolen mit einer Menge von Nichtterminalsymbolen N, gibt dabei vor, welche Symbole dafür verwendet werden können. Die Menge der Terminalsymbole definiert, aus welchen Zeichen Wörter bestehen, die nicht weiter abgeleitet werden können. Diese Wörter ergeben zusammengenommen die von der Grammatik beschriebene formale Sprache. Das Startsymbol muss dagegen ein Nichtterminalsymbol sein. Zusätzliche Nichtterminalsymbole erlauben differenziertere Regeln.
Produktionsregeln sind definitionsgemäß geordnete Paare ( α, β ), die auch α → β geschrieben werden. Man wendet sie auf eine Zeichenfolge w an, indem ein Vorkommen der Zeichenfolge α in w durch β ersetzt wird. Auf der linken Seite der Regel muss immer mindestens ein Nichtterminalsymbol stehen. Eine Menge von Regeln mit gleicher linker Seite, also α → β1, ..., α → βn, wird abkürzend auch als α → β1, ⎮... ⎮ βn geschrieben.
Zum Beispiel kann man mit der Regelmenge X → ＋ ⎮ － die Zeichenfolge 1X 2 entweder zu 1 ＋ 2 oder zu 1 － 2 ableiten.
Ebenso wie auf eine gegebene Zeichenfolge mehrere Regeln gleichzeitig anwendbar sein können, muss es nicht immer nur eine Stelle in der Zeichenfolge geben, auf die eine Regel passt. Formale Grammatiken schreiben keine Reihenfolge vor. Alle nur aus Terminalsymbolen bestehenden Wörter, die sich aus dem Startsymbol ableiten lassen, zählen zur von der Grammatik beschriebenen Sprache.