- Post Kalkül
-
Der vom polnisch-US-amerikanischen Mathematiker Emil Leon Post entwickelte Post-Kalkül zählt zu den Wortverarbeitenden Kalkülen. Diese beschreiben, wie durch formale Umwandlung von Zeichenketten, ein bestimmtes Ergebnis erzielt werden kann. Eine Kenntnis über die spezifischen Bedeutung der Zeichenkette ist hierbei unnötig.
Inhaltsverzeichnis
Definition und Funktionsweise
Eine Menge von Regeln, durch die bestimmte Zeichenketten in neue Zeichenketten umgewandelt werden können, ist die Grundlage aller mathematischen oder logischen Systeme. Der Post-Kalkül verwendet Substitutionsregeln, die beidseitig aus einer Folge von Variablen und Konstanten bestehen. Die übrigen wortverarbeitenden Kalküle definieren weniger allgemeine Regeln zur Substitution. Der Kanonische Post-Kalkül besitzt nachfolgende Form.
u1V1u2V2 ... umVmum+1 → w1V'1w2V'2 ... wnV'nwn+1
V1, V2 ... Zm sind Variablen, es gilt {V'1...V'n} ⊆ {V1...Vn}
u1, u2 ... um, um+1, w1, w2 ... wm, wm+1 sind Teilworte des Ausgangswortes
Dabei gibt der Index m die Variablenanzahl auf der linken Regelseite und n die Variablenanzahl auf der rechten Regelseite an. Die Variablen der rechten Regelseite stellen eine Teilmenge der linken Regelseite dar. Die Reihenfolge der Variablen der rechten Regelseite darf sich von der Reihenfolge der linken Regelseite unterscheiden. Darüber hinaus kann jede Variable der linken Regelseite, mehr als einmal auf die rechte Regelseite übertragen werden (n >= m). Es darf eine unbegrenzte Anzahl an Variablen genutzt werden. Alle definierten Regeln werden stets auf das gesamte Ausgangswort angewendet.
Der Kanonische Post-Kalkül ist ein nichtdeterministischer Kalkül und besitzt die nachfolgenden Eigenschaften.
- Bei Verarbeitung eines Eingabewortes werden alle anwendbaren Regeln parallel angewendet.
- Die Ergebnisse der nichtdeterministischen Verarbeitung werden in einer Baumstruktur abgelegt.
- Beim Pattern Matching kann es mehrere Möglichkeiten für die Variablenbelegung geben.
- Die Verarbeitung eines Teilbaumes wird beendet, sobald keine Regel mehr auf ihn anwendbar ist.
- Kann keiner der Teilbäume weiter bearbeitet werden, so ist die Verarbeitung des Eingebewortes beendet.
Einfaches Fallbeispiel
> EINGABEWORT possibility > REGELN R1 po[A]s[B]ibility -> [B]foo[A] R2 po[A]i[B]i[C]y -> [A][C]bar[B]xorize R3 s[A]o[B] -> foos > TABELLE Eingabewort | [A] | [B] | [C] | Ausgabewort | Regel | Level ----------------+-----------+------+-----+-----------------+-------+------ possibility | s | / | / | foos | R1 | L0 " | / | s | / | sfoo | R1 | L0 " | ssib | l | t | ssibtbarlxorize | R2 | L0 " | ss | bil | t | sstbarbilxorize | R2 | L0 " | ss | b | lit | sslitbarbxorize | R2 | L0 ----------------+-----------+------+-----+-----------------+-------+------ sfoo | fo | / | / | foos | R3 | L1 " | f | o | / | foos | R3 | L1 ssibtbarlxorize | sibtbarlx | rize | / | foos | R3 | L1 sstbarbilxorize | stbarbilx | rize | / | foos | R3 | L1 sslitbarbxorize | slitbarbx | rize | / | foos | R3 | L1 > BAUM /-------------\ | possibility | L0 \-------+-----/ | V /----------+----- .. -----+---------------------\ | | | | | R1 | R1 | R2 | R2 | | | | V V V V /------\ /------\ /-----------------\ /-----------------\ | foos | | sfoo | | sstbarbilxorize | | sslitbarbxorize | L1 \------/ \--+---/ \--+--------------/ \--+--------------/ | | | | R3 | R3 | R3 | | | \------ .. ----+---------------------/ | V /------\ | foos | L2 \------/Anwendungsbeispiele
Addition von Unärzahlen
> Eingabewort ||||||+||||||||+|+|| > Regel [A]+[B]->[A][B] > Ergebnis |||||||||||||||||
Subtraktion von Unärzahlen
> Eingabewort |||||-||| > Regeln [A]|-[B]|->[A]-[B] [A]-->[A] > Ergebnis ||
Multiplikation von Unärzahlen
> Eingabewort |||*||||= > Regeln |[A]*[B]=[C]->[A]*[B]=[C][B] *[A]=[B]->[B] > Ergebnis ||||||||||||
Parität prüfen
> Eingabewort 101010 > Regeln [A]00[B]->[A]0[B] [A]01[B]->[A]1[B] [A]10[B]->[A]1[B] [A]11[B]->[A]0[B] > Ergebnis 1
Siehe auch
Weblinks
- Post-Kalkül Interpreter (englisch)
Wikimedia Foundation.
