In der Informatik werden Probleme häufig als Sprachen1formuliert, um es formalen Methoden zugänglich zu machen. Eine Sprache entsteht durch die Definition einer Grammatik, die das Problembeschreibt. Eine Grammatik ist worterzeugendes, formales Konstrukt, der folgenden Gestalt:
Unter der Menge V versteht man dabei Variablen, die während des Ableitungsprozesses verwendet werden. Das Ergebnis einer Ableitung ist ein Wort aus der Sprache der Grammatik. Dieses enthält nur noch Elemente aus ∑. Eine Ableitung eines Wortes ist der Prozess des sukessiven Anwendens von Produktionen p ∈ P. Um dies zu verstehen, sei der Begriff der Ableitung formler gefasst.
Ein Ableitungsschritt ist eine Anwendung einer Produktion p ∈ P. Dadurch wird eine Relation ⇒ ⊆ (V ∪)* × (V ∪)* definiert, wobei u = aBc⇒v = abc genau dann gilt, wenn a,b,c ∈ ∑, B ∈ V und B →b ∈ P also die entsprechende Produktion angewendet wurde.
Ein Beispiel soll den Prozess des Ableitens verdeutlichen. Sei dafür G = ({A,B,C},{a,b,c},{AB → abC,C → c},A}. Das Wort abc wird durch die Ableitung:
in zwei Ableitungsschritten erzeugt. Die Sprache L(G), die durch die Grammatik G erzeugt wird, wird durch die reflexive, transitive Hülle ⇒ *:= ∪n>0 ⇒n der Relation ⇒ definiert, also:
An dieser Stelle sei noch auf einige Schreibweisen eingegangen werden. Sei dazu ∑ eine Menge von Terminalzeichen. Mit ∑n ist die Menge aller Wörter, enstanden mit Elementen aus ∑, der Länge n verstanden, also:
Ferner verwendet man noch die Abkürzungen:
Eine weitere wichtige Funktion, die im Zusammenhang mit der Hürde einer Feuersequenz verwendet wird, ist das PARIKH-Bild P(σ) eines Wortes σ ∈ ∑*. Diese Funktion ist durch:
definiert,wobei #a(σ) die Anzahl des Zeichens a im Wort σ und ∑={a1,a2, . . . ,an} ist. Das PARIKH-Bild eines Wortes gibt somit einen Vektor an, dessen Komponenten die Anzahl des Vorkommens eines Zeichens in diesem Wort ist. Dies führt zur folgenden, vereinfachten Schreibweise:
 |
Glossar 
Forschungsprojekte 
Anbieterverzeichnis 
Datenbanksuche 
Highlights 
Eintrag kommentieren