imported>Aka: Halbgeviertstrich, Links optimiert

2018-10-10T20:03:48Z

Halbgeviertstrich, Links optimiert

Neue Seite

Unter einem '''Erzeugungssystem''' (nicht: [[Erzeugendensystem]]) versteht man in der [[Mathematik]] ein formales System, das aus einer [[Menge (Mathematik)|Ausgangsmenge]] und einer oder mehreren ''Erzeugungsregeln'' besteht. Die Elemente der Ausgangsmenge bezeichnet man auch als [[Axiom]]e. Durch die Anwendung der Erzeugungsregeln lassen sich aus der Ausgangsmenge neue [[Element (Mathematik)|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 [[Zahlenbereich]]e, [[Baum (Graphentheorie)|Bäume]], [[Term]]e, [[Formel]]n oder [[formale Sprache|Sprachen]] handeln. Ein einfaches Beispiel zeigt, wie die Menge der natürlichen Zahlen <math>\mathbb{N}</math> mittels eines Erzeugungssystems konstruiert werden kann:

* Die Ausgangsmenge A sei <math>\{0\} \subseteq \mathbb{N}</math>
* Erzeugungsregel: Aus jedem x darf x + 1 erzeugt und der Ausgangsmenge hinzugefügt werden.

Ein weiteres bekanntes Beispiel für Erzeugungssysteme bilden die [[formale Grammatik|formalen Grammatiken]] der [[Chomsky-Hierarchie]] – die Erzeugnisse sind in diesem Fall [[formale Sprache]]n. 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]].

[[Kategorie:Mathematische Logik]]
[[Kategorie:Theoretische Informatik]]

Erzeugungssystem - Versionsgeschichte

imported>Aka: Halbgeviertstrich, Links optimiert