imported>Invisigoth67: typo

2025-02-22T07:40:28Z

typo

Neue Seite

Der vom polnisch-US-amerikanischen Mathematiker [[Emil Leon Post]] entwickelte '''Post-Kalkül''' zählt zu den Wortverarbeitenden [[Kalkül]]en. Diese beschreiben, wie durch formale Umwandlung von [[Zeichenkette]]n, ein bestimmtes Ergebnis erzielt werden kann. Eine Kenntnis über die spezifischen Bedeutung der Zeichenkette ist hierbei unnötig.

== 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 [[Substitution (Mathematik)|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 … Vm 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 [[Determinismus (Algorithmus)|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 [[Baum]]struktur 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: <code>possibility</code>
;Regeln:
: <code>R1 po[A]s[B]ibility → [B]foo[A]</code>
: <code>R2 po[A]i[B]i[C]y → [A][C]bar[B]xorize</code>
: <code>R3 s[A]o[B] → foos</code>

;Tabelle:
{| class="wikitable" style="font-family:monospace; border:2px solid #000000;"
|-style="border-bottom:2px solid #000000;"
! Eingabewort
! [A]
! [B]
! [C]
! Ausgabewort
! Regel
! Level
|-
| possibility || s || / || / || foos || R1 || L0
|-
| possibility || s || / || / || sfoo || R1 || L0
|-
| possibility || ssib || l || t || ssibtbarlxorize || R2 || LO
|-
| possibility || ss || bil || t || ssibtbarlxorize || R2 || LO
|- style="border-bottom:2px solid #000000;"
| possibility
| ss
| b
| lit
| ssibtbarlxorize
| R2
| LO
|-
| sfoo || fo || / || / || foos || R3 || L1
|-
| sfoo || f || o || / || foos || R3 || L1
|-
| ssibtbarlxorize || sibtbarlx || rize || / || foos || R3 || L1
|-
| ssibtbarlxorize || sibtbarlx || rize || / || foos || R3 || L1
|-
| ssibtbarlxorize || sibtbarlx || rize || / || foos || R3 || L1
|}

;Baum:

<syntaxhighlight lang="text">
┌─────────────┐
L0 │ possibility │
└──────┬──────┘
│↓
┌──┴─────┬───────────────┬────────────────────┐
│ │ │ │
│ R1 │ R1 │ R2 │ R2
│↓ │↓ │↓ │↓
┌───┴──┐ ┌──┴───┐ ┌────────┴────────┐ ┌────────┴────────┐
L1 │ foos │ │ sfoo │ │ sstbarbilxorize │ │ sstbarbilxorize │
└──────┘ └──┬───┘ └────────┬────────┘ └────────┬────────┘
│ │ │
│ R3 │ R3 │ R3
│ │ │
└───────────────┼────────────────────┘
│↓
┌───┴──┐
L2 │ foos │
└──────┘
</syntaxhighlight>

== Anwendungsbeispiele ==
=== Addition von Unärzahlen ===
* Eingabewort
: <code>||||||+||||||||+|+||</code>
* Regel
:<code>[A]+[B]→[A][B]</code>
* Ergebnis
: <code>|||||||||||||||||</code>

=== Subtraktion von Unärzahlen ===
* Eingabewort
: <code>|||||-|||</code>
* Regeln
:<code>[A]|-[B]|→[A]-[B]</code>
: <code>[A]→[A]</code>
* Ergebnis
: <code>||</code>

=== Multiplikation von Unärzahlen ===
* Eingabewort
: <code>|||*||||=</code>
* Regeln
: <code>|[A]*[B]=[C]→[A]*[B]=[C][B]</code>
: <code>*[A]=[B]→[B]</code>
* Ergebnis
: <code>||||||||||||</code>

=== Parität prüfen ===
* Eingabewort
: <code>101010</code>
* Regeln
: <code>[A]00[B]→[A]0[B]</code>
: <code>[A]01[B]→[A]1[B]</code>
: <code>[A]10[B]→[A]1[B]</code>
: <code>[A]11[B]→[A]0[B]</code>
* Ergebnis
: <code>1</code>

== Siehe auch ==

* [[Semi-Thue-System]]
* [[Markow-Algorithmus]]

== Weblinks ==
* [https://freeshell.de//~jcm/index.php?nav=projects Post-Kalkül Interpreter] (englisch)

[[Kategorie:Theoretische Informatik]]
[[Kategorie:Algorithmus]]

Post-Kalkül - Versionsgeschichte

imported>Invisigoth67: typo