Erzeugungssystem

Unter einem Erzeugungssystem (nicht: Erzeugendensystem) versteht man in der Mathematik ein formales System, das aus einer Ausgangsmenge und einer oder mehreren Erzeugungsregeln besteht. Die Elemente der Ausgangsmenge bezeichnet man auch als Axiome. Durch die Anwendung der Erzeugungsregeln lassen sich aus der Ausgangsmenge neue Elemente gewinnen, welche zur Ausgangsmenge hinzugefügt werden. Auf diese erweiterte Menge können die Regeln abermals angewandt werden. Dieser Prozess wird iterativ so lange wiederholt, bis eine gewünschte Menge, das Erzeugnis, abgeleitet wurde.

Erzeugungssysteme dienen in sehr verschiedenen Zusammenhängen der konstruktiven Definition von Mengen. Bei diesen Mengen kann es sich etwa um Zahlenbereiche, Bäume, Terme, Formeln oder Sprachen handeln. Ein einfaches Beispiel zeigt, wie die Menge der natürlichen Zahlen $\mathbb{N}$ mittels eines Erzeugungssystems konstruiert werden kann:

• Die Ausgangsmenge A sei $\{0\} \subseteq \mathbb{N}$
• Erzeugungsregel: Aus jedem x darf x + 1 erzeugt und der Ausgangsmenge hinzugefügt werden.

Ein weiteres bekanntes Beispiel für Erzeugungssysteme bilden die formalen Grammatiken der Chomsky-Hierarchie - die Erzeugnisse sind in diesem Fall formale Sprachen. Weiterhin bilden logische Kalküle eine wichtige Klasse von Erzeugungssystemen, die man auch als Beweissysteme bezeichnet. Aufgrund ihres konstruktiven und damit anwendungsnahen Charakters spielen unterschiedliche Erzeugungssysteme eine bedeutsame Rolle in der Informatik.