Ableitung (Informatik)

Als Ableitung wird in der theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu erzeugen.

Unter einem Wort versteht man eine beliebige Zeichenkette, also eine endliche Folge von Symbolen. Eine formale Grammatik ist ein mathematisches Modell, das eine Menge solcher ableitbaren Wörter festlegt. Diese Menge nennt man eine formale Sprache. Das einmalige Ersetzen von einem Teilabschnitt einer Zeichenkette, gemäß einer der Regeln der formalen Grammatik, stellt einen Ableitungsschritt dar. Durch die formale Grammatik werden auch die Symbole festgelegt, aus denen ein Wort bestehen darf, und solche, die alleine in den Zwischenergebnissen der Ableitung eines Wortes auftreten dürfen. Zum Ableiten eines Wortes beginnt man mit einem besonderen Symbol, dem Startsymbol, und führt dann nacheinander Ableitungsschritte durch (bei Wahl geeigneter Regeln), bis schließlich das Wort erzeugt worden ist.


From Wikipedia, the free encyclopedia · View on Wikipedia

Developed by Tubidy