Index

Wahlpflichtthemen

2. Formale Sprachen (8)


Semi-Thue-Systeme

Einführung

Bisher haben wir erkennende Automaten im Zusammenhang mit den Sprachen kennengelernt, also analysierende Systeme, d.h. Systeme, welche feststellen können, ob ein Wort zu einer Sprache gehört. Im Folgenden geht es nun um erzeugende Systeme, die also in der Lage sind, Wörter einer Sprache zu erzeugen.

Eine mögliche Beschreibung solcher erzeugenden Systeme sind Semi-Thue-Systeme (A. Thue, 1914).

Ein Semi-Thue-System wird definiert an Hand eines Regelwerkes genannt Produktionen, welche eine Menge von Relationen (R) der Form x -> y darstellen, wobei x,y Î E*.

Dabei gilt:
Ein Wort u ist unmittelbar überführbar in v (u => v), wenn es eine Regel x -> y Î R gibt und u bzw. v in der Form u = wxz bzw. v = wyz darstellbar sind mit u,v,w,x,y,z Î E*.
u ist überführbar in v (u =>* v), wenn gilt: u => w1 => w2... => v.

Beispiel

Im allgemeinen ist es problematisch, für zwei beliebige Worte u und v zu entscheiden, ob es eine Überführung u =>* v gibt.
Seit der Mitte des letzten Jahrhunderts weiß man, dass es kein allgemeines Verfahren für beliebige Semi-Thue-Systeme geben kann. Für konkrete Systeme, können jedoch durchaus Verfahren bestehen.

Weitere Beispiele

 

[Index] [Zurück/l-Automaten] [Fortsetzung/Chomsky-Grammatiken]


Autor: Jürgen Dehmer
Letzte Änderung: