„Automatenmodell“ – Versionsunterschied
| [ungesichtete Version] | [ungesichtete Version] |
YMS (Diskussion | Beiträge) K +Redundanz |
Keine Bearbeitungszusammenfassung |
||
| (Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
| Zeile 3: | Zeile 3: | ||
In der [[Theoretische Informatik|theoretischen Informatik]] werden zwei Kategorien, nämlich die deterministischen und die nichtdeterministischen Automaten, und drei grundsätzliche Klassen unterschieden, nämlich die endlichen Automaten, die stapelverarbeitenden Kellermaschinen und die mit beidseitig unendlichem Band ausgestatteten Turingmaschinen. Diese '''Automatenmodelle''' stehen in einer logischen Beziehung zu den Sprachklassen und finden dort ihre formale Entsprechung. |
In der [[Theoretische Informatik|theoretischen Informatik]] werden zwei Kategorien, nämlich die deterministischen und die nichtdeterministischen Automaten, und drei grundsätzliche Klassen unterschieden, nämlich die endlichen Automaten, die stapelverarbeitenden Kellermaschinen und die mit beidseitig unendlichem Band ausgestatteten Turingmaschinen. Diese '''Automatenmodelle''' stehen in einer logischen Beziehung zu den Sprachklassen und finden dort ihre formale Entsprechung. |
||
== |
== anschauliche Vorstellungen == |
||
''' Endlicher Automat ''' |
|||
Ein Fahrkartenautomat gehört zur Klasse der endlichen Automaten. Er hat als Eingabealphabet verschiedene Tasten, einen Kartenleser mit endlichem Magnetband und einen einfachen Timer. Er hat einen Anfangszustand mit Willkommensmeldung, reagiert auf die Reihenfolge der Eingaben des genannten Alphabets und erreicht einen Endzustand, wenn die Fahrkarte gedruckt wird. |
Ein Fahrkartenautomat gehört zur Klasse der endlichen Automaten. Er hat als Eingabealphabet verschiedene Tasten, einen Kartenleser mit endlichem Magnetband und einen einfachen Timer. Er hat einen Anfangszustand mit Willkommensmeldung, reagiert auf die Reihenfolge der Eingaben des genannten Alphabets und erreicht einen Endzustand, wenn die Fahrkarte gedruckt wird. |
||
''' Kellerautomat ''' |
|||
Wenn Spielkarten auf einem Stapel abgelegt werden und in umgekehrter Reihenfolge wieder gezogen werden, ist damit prinzipiell ein endlicher Kellerspeicher realisiert. Nach demselben Prinzip arbeitet auch eine Kellermaschine, jedoch mit unendlichem Stapel. Sie hat ebenfalls ein Eingabealphabet - die Spielkartenbilder - und reagiert programmiert auf diese Eingaben. Sie ist intelligenter als ein endlicher Automat, weil sie über einen unendlichen Speicher, den sogenannten Keller, verfügt. Siehe auch das Beispiel [[umgekehrte polnische Notation]]. |
Wenn Spielkarten auf einem Stapel abgelegt werden und in umgekehrter Reihenfolge wieder gezogen werden, ist damit prinzipiell ein endlicher Kellerspeicher realisiert. Nach demselben Prinzip arbeitet auch eine Kellermaschine, jedoch mit unendlichem Stapel. Sie hat ebenfalls ein Eingabealphabet - die Spielkartenbilder - und reagiert programmiert auf diese Eingaben. Sie ist intelligenter als ein endlicher Automat, weil sie über einen unendlichen Speicher, den sogenannten Keller, verfügt. Siehe auch das Beispiel [[umgekehrte polnische Notation]]. |
||
''' Turingmaschine ''' |
|||
Wenn man nun auf den unendlichen Stapel der Kellermaschine eine beliebige Zugriffsreihenfolge erlaubt, also Herausgreifen aus der Mitte des Stapels oder etwa der untersten Karte, erhält man einen noch intelligenteren Automaten, welcher nach dem englischen Mathematiker [[Alan Turing]] benannt ist. Es ist eine bisher nicht widerlegte These, die Churchsche These, dass man grundsätzlich mit einem solchen Automaten alle denkbaren Berechnungen durchführen kann. In der Praxis wird dieses Modell allerdings so gut wie gar nicht eingesetzt, weil es sehr langsam und speicherhungrig ist und man im Laufe der Jahrzehnte optimierte Methoden der Berechnung entwickelt hat. |
Wenn man nun auf den unendlichen Stapel der Kellermaschine eine beliebige Zugriffsreihenfolge erlaubt, also Herausgreifen aus der Mitte des Stapels oder etwa der untersten Karte, erhält man einen noch intelligenteren Automaten, welcher nach dem englischen Mathematiker [[Alan Turing]] benannt ist. Es ist eine bisher nicht widerlegte These, die Churchsche These, dass man grundsätzlich mit einem solchen Automaten alle denkbaren Berechnungen durchführen kann. In der Praxis wird dieses Modell allerdings so gut wie gar nicht eingesetzt, weil es sehr langsam und speicherhungrig ist und man im Laufe der Jahrzehnte optimierte Methoden der Berechnung entwickelt hat. |
||
== sprachliche Beschreibungen == |
|||
''' Endlicher Automat ''' |
|||
Der endliche Automat entspricht einem regulären Sprachmuster, das in Stufe 3 der Chomsky-Hierarchie beschreibbar ist. Hierunter versteht man eine Grammatik, deren Symbole sich aus Variablen, den Nonterminalen, und Konstanten, den Terminalen, zusammensetzen. Nonterminale dürfen durch eine Folge von Symbolen - ohne einfache Selbstersetzung, also ohne primitive Rekursion - ersetzt werden. |
|||
''' Kellerautomat ''' |
|||
Dem Kellerautomaten entspricht eine Grammatik auf Stufe 2, in der einfache Selbstersetzung, also primitive Rekursion, auftreten darf. |
|||
''' Turingmaschine ''' |
|||
Die Turingmaschine ist durch eine Grammatik der Stufe 0 gleichbedeutend beschreibbar. |
|||
== technische Modelle == |
|||
''' Endlicher Automat ''' |
|||
Der endliche Automat entspricht einem gerichteten Graphen mit Zuständen (Plätzen) und Übergängen (Transitionen). |
|||
[[Bild:Nea02.png|thumb|[[Endlicher Automat]]]] |
|||
''' Kellerautomat ''' |
|||
Die Kellermaschine entspricht zwei Bändern und einem Rechenwerk, Das Eingabeband ist nur in einer Richting lesbar und nicht beschreibbar. Das kellerband läßt sich nur in einer Richtung beschreiben und es ist nur das äußerste Element lesbar. |
|||
[[Bild:Kellerautomat.png|thumb|[[Kellerautomat]]]] |
|||
''' Turingmaschine ''' |
|||
Für die Turringmaschine hat man sich ein links und rechts unbeschränktes Band vorzustellen, das über eine Markierung verfügt, die auf das Element verweist, das gerade lesbar und beschreibbar ist. Von der Markierung aus darf jeweils ein Schritt nach links oder rechts getan werden. |
|||
[[Bild:Turingmaschine.png|thumb|[[Turingmaschine]]]] |
|||
== Determinismus == |
== Determinismus == |
||
Version vom 26. März 2008, 20:51 Uhr
In der theoretischen Informatik werden zwei Kategorien, nämlich die deterministischen und die nichtdeterministischen Automaten, und drei grundsätzliche Klassen unterschieden, nämlich die endlichen Automaten, die stapelverarbeitenden Kellermaschinen und die mit beidseitig unendlichem Band ausgestatteten Turingmaschinen. Diese Automatenmodelle stehen in einer logischen Beziehung zu den Sprachklassen und finden dort ihre formale Entsprechung.
anschauliche Vorstellungen
Endlicher Automat Ein Fahrkartenautomat gehört zur Klasse der endlichen Automaten. Er hat als Eingabealphabet verschiedene Tasten, einen Kartenleser mit endlichem Magnetband und einen einfachen Timer. Er hat einen Anfangszustand mit Willkommensmeldung, reagiert auf die Reihenfolge der Eingaben des genannten Alphabets und erreicht einen Endzustand, wenn die Fahrkarte gedruckt wird.
Kellerautomat Wenn Spielkarten auf einem Stapel abgelegt werden und in umgekehrter Reihenfolge wieder gezogen werden, ist damit prinzipiell ein endlicher Kellerspeicher realisiert. Nach demselben Prinzip arbeitet auch eine Kellermaschine, jedoch mit unendlichem Stapel. Sie hat ebenfalls ein Eingabealphabet - die Spielkartenbilder - und reagiert programmiert auf diese Eingaben. Sie ist intelligenter als ein endlicher Automat, weil sie über einen unendlichen Speicher, den sogenannten Keller, verfügt. Siehe auch das Beispiel umgekehrte polnische Notation.
Turingmaschine Wenn man nun auf den unendlichen Stapel der Kellermaschine eine beliebige Zugriffsreihenfolge erlaubt, also Herausgreifen aus der Mitte des Stapels oder etwa der untersten Karte, erhält man einen noch intelligenteren Automaten, welcher nach dem englischen Mathematiker Alan Turing benannt ist. Es ist eine bisher nicht widerlegte These, die Churchsche These, dass man grundsätzlich mit einem solchen Automaten alle denkbaren Berechnungen durchführen kann. In der Praxis wird dieses Modell allerdings so gut wie gar nicht eingesetzt, weil es sehr langsam und speicherhungrig ist und man im Laufe der Jahrzehnte optimierte Methoden der Berechnung entwickelt hat.
sprachliche Beschreibungen
Endlicher Automat Der endliche Automat entspricht einem regulären Sprachmuster, das in Stufe 3 der Chomsky-Hierarchie beschreibbar ist. Hierunter versteht man eine Grammatik, deren Symbole sich aus Variablen, den Nonterminalen, und Konstanten, den Terminalen, zusammensetzen. Nonterminale dürfen durch eine Folge von Symbolen - ohne einfache Selbstersetzung, also ohne primitive Rekursion - ersetzt werden.
Kellerautomat Dem Kellerautomaten entspricht eine Grammatik auf Stufe 2, in der einfache Selbstersetzung, also primitive Rekursion, auftreten darf.
Turingmaschine Die Turingmaschine ist durch eine Grammatik der Stufe 0 gleichbedeutend beschreibbar.
technische Modelle
Endlicher Automat
Der endliche Automat entspricht einem gerichteten Graphen mit Zuständen (Plätzen) und Übergängen (Transitionen).
Kellerautomat
Die Kellermaschine entspricht zwei Bändern und einem Rechenwerk, Das Eingabeband ist nur in einer Richting lesbar und nicht beschreibbar. Das kellerband läßt sich nur in einer Richtung beschreiben und es ist nur das äußerste Element lesbar.
Turingmaschine
Für die Turringmaschine hat man sich ein links und rechts unbeschränktes Band vorzustellen, das über eine Markierung verfügt, die auf das Element verweist, das gerade lesbar und beschreibbar ist. Von der Markierung aus darf jeweils ein Schritt nach links oder rechts getan werden.
Determinismus
Zu allen drei Klassen sind jeweils deterministische, also vorhersagbare, als auch nichtdeterministische, also von vornherein unbestimmbare, nichtdeterministische Modelle vorstellbar. Wenn man jedoch der Unbestimmtheit eines Zustandsüberganges eine gewisse Wahrscheinlichkeit zuordnen kann, kommt man zu stochastischen Automaten bzw. den Markov-Ketten.
