„Wort (Theoretische Informatik)“ – Versionsunterschied
| [ungesichtete Version] | [ungesichtete Version] |
Keine Bearbeitungszusammenfassung |
K Klaus verschob die Seite Wort (theoretische Informatik) nach Wort (Theoretische Informatik), ohne dabei eine Weiterleitung anzulegen |
(kein Unterschied)
| |
Aktuelle 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.