Eintrag kommentierenEintrag bewerten
Dieser Eintrag wurde im Schnitt mit 0 von 5 Punkten bewertet
Glossareintrag
Sprachen
Glossar:27262
Externe Quellen zum Thema NEU: Externe Quellen zum Thema suchen 
Erläuterung
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:

Definition 26


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:

Ableitung


in zwei Ableitungsschritten erzeugt. Die Sprache L(G), die durch die Grammatik G erzeugt wird, wird durch die reflexive, transitive Hülle ⇒ *:= ∪n>0n der Relation ⇒ definiert, also:

Grammatik


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:

Summe


Ferner verwendet man noch die Abkürzungen:

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:

Wort


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:

vereinfacht
Externe Quellen zum Thema NEU: Externe Quellen zum Thema suchen 
 Eintrag kommentieren 
 Eintrag bewerten 
Zu dieser Seite wurden noch keine Kommentare oder Bewertungen abgegeben.
 
Zum Seitenanfang Top Drucken Impressum AGB
Home

VSEK ©2001-2018