In der theoretischen Informatik ist ein Algorithmus von Markov ein Schnur-Neuschreiben-System, das einer Grammatik ähnliche Regeln verwendet, auf Reihen von Symbolen zu funktionieren. Wie man gezeigt hat, sind Algorithmen von Markov Turing-abgeschlossen gewesen, was bedeutet, dass sie als ein allgemeines Modell der Berechnung passend sind und jeden mathematischen Ausdruck aus seiner einfachen Notation vertreten können. Algorithmen von Markov werden nach dem Mathematiker Andrey Markov der Jüngere genannt.

Refal ist eine auf Algorithmen von Markov gestützte Programmiersprache.

Algorithmus

Die Regeln sind eine Folge des Paares von Schnuren, die gewöhnlich in der Form des Musters &rarr präsentiert sind; Ersatz. Einige Regeln können enden.

In Anbetracht einer Eingangsschnur:

1. Überprüfen Sie die Regeln, um von oben bis unten zu sehen, ob einige der Muster in der Eingangsschnur gefunden werden kann.
2. Wenn niemand, der Algorithmus-Halt gefunden wird.
3. Wenn ein (oder mehr) gefunden wird, verwenden Sie den ersten von ihnen, um den leftmost das Zusammenbringen des Textes in der Eingangsschnur mit seinem Ersatz zu ersetzen.
4. Wenn die angewandte Regel eine endende, der Algorithmus-Halt war.
5. Kehren Sie zum Schritt 1 zurück und fahren Sie fort.

Beispiel

Das folgende Beispiel zeigt die grundlegende Operation eines Algorithmus von Markov.

Regeln

1. "A"-> "Apfel"
2. "B"-> "Tasche"
3. "S"-> "Geschäft"
4. "T"-> "der"
5. "das Geschäft"-> "mein Bruder"
6. "nie verwendet"->. "Regel" begrenzend

Symbol-Schnur

"Ich habe einen B Als von T S." gekauft

Ausführung

Wenn der Algorithmus auf das obengenannte Beispiel angewandt wird, wird sich die Symbol-Schnur in die folgende Weise ändern.

1. "Ich habe einen B von Äpfeln von T S." gekauft
2. "Ich habe eine Tasche von Äpfeln von T S." gekauft
3. "Ich habe eine Tasche von Äpfeln vom T Geschäft gekauft."
4. "Ich habe eine Tasche von Äpfeln vom Geschäft gekauft."
5. "Ich habe eine Tasche von Äpfeln von meinem Bruder gekauft."

Der Algorithmus wird dann enden.

Ein anderes Beispiel

Diese Regeln führen ein interessanteres Beispiel an. Sie schreiben Binärzahlen zu ihren unären Kollegen um. Zum Beispiel: 101 wird zu einer Reihe von 5 Konsekutivbars umgeschrieben.

Regeln

1. "0"-> "0"
2. "1"-> "0"
3. "0"-> ""

Symbol-Schnur

"101"

Ausführung

Wenn der Algorithmus auf das obengenannte Beispiel angewandt wird, wird er nach den folgenden Schritten enden.

1. "001"

"001"

1. "000"

"000""000"

1. "00"
2. "0"
3. ""

• Caracciolo di Forino, A. Schnur-Verarbeitungssprachen und verallgemeinerte Algorithmen von Markov. Auf Symbol-Manipulationssprachen und Techniken, D. G. Bobrow (Hrsg.). Nordhollander Publ. Co. Amsterdam, Die Niederlande, 1968, Seiten 191-206.
• Andrey Andreevich Markov (1903-1979) 1960. Die Theorie von Algorithmen. Amerikanische Mathematische Gesellschaftsübersetzungen, Reihe 2, 15, 1-14.

Links

• Der Online-Algorithmus-Dolmetscher von Markov

• Algorithmus-Dolmetscher von Markov
• Algorithmus-Dolmetscher von Markov