Automatentheorie - Revision history

NBlöcher: Marked as {{ref}}

2014-06-18T17:53:28Z

Marked as {{ref}}

Haspelmath at 15:19, 24 July 2008

2008-07-24T15:19:31Z

Okolowski: New page: == Ursprung == *''griech. automatos'' - sich von selbst bewegend == Definition == Die Automatentheorie befasst sich mit der formalen mathematischen Beschreibung und Untersuchung von [[Au...

2008-07-16T13:32:40Z

New page: == Ursprung == *''griech. automatos'' - sich von selbst bewegend == Definition == Die Automatentheorie befasst sich mit der formalen mathematischen Beschreibung und Untersuchung von [[Au...

New page

== Ursprung ==
*''griech. automatos'' - sich von selbst bewegend

== Definition ==
Die Automatentheorie befasst sich mit der formalen mathematischen Beschreibung und Untersuchung von [[Automaten]], d.h. von Modellen diskreter sequentieller informationsverarbeitender Systeme. Die Automatentheorie befasst sich weniger mit der internen Struktur als mit dem Verhalten solcher Systeme; dies wird wiederum darauf reduziert, welche Folgen von Eingaben in das System welche Ausgaben erzeugen können. Bei unendlichen (wachsenden) Automaten spielt jedoch auch die Art und Weise des Wachstums eine wichtige Rolle. Bei Automaten mit potentiell unendlichem Speicher ist die Art des Speicherzugriffs und die Folge der Speicherinhalte wichtig.
Oft werden akzeptierende Automaten ([[Akzeptor]]) betrachtet, bei denen nur ihre akzeptierte Wortmenge interessiert, d.h. die Menge endlicher Eingabefolgen (Wörter), die den Automat von einem (oder mehreren) Anfangszuständen in einen von (im allgemeinen) mehreren Endzuständen überführen; die Ausgabe besteht also jeweils nur aus einem ''Ja'' oder ''Nein'' nach Ende der Eingabe. Symmetrisch dazu werden auch erzeugende Automaten ([[Generator]]) betrachtet.
Ferner behandelt man nicht nur [[deterministisch]] arbeitende Automaten (bei denen die Änderung des jeweiligen Zustands und die jeweilige Ausgabe funktional nur von der momentanen Eingabe und dem aktuellen Zustand abhängt), sondern auch [[Nicht-Determinismus|nicht-deterministische Automaten]], bei denen Relationen anstelle von Funktionen die mögliche Arbeitsweise beschreiben.
Bei der Beschreibung nicht-deterministischer Automaten ist es erlaubt, dass zu einem Paar aus momentaner Eingabe und aktuellem Zustand mehrere mögliche Nachfolgezustände und Angaben angegeben werden, wobei im konkreten Ablauf jeweils nicht-deterministisch eine Wahl getroffen werden muss. So wird also von einem nicht-deterministischen Akzeptor eine Eingabefolge genau dann akzeptiert, wenn sie bei geschickter Auswahl aus den jeweils erlaubten Folgezuständen von einem der Anfangs- zu einem der Endzustände führen kann.
Klassen von Akzeptoren entsprechen Klassen von Wortmengen (d.h. [[formale Sprachen]]). Die bekannteste Klasseneinteilung bei Akzeptoren erfolgt über die Art der Speicher:

* Endliche Akzeptoren ([[endlicher Automat|endliche Automaten]]) haben endliche Speicherkapazität, die von ihnen akzeptierbaren Wortmengen sind die [[reguläre Sprachen|regulären Sprachen]];
* Akzeptoren mit Kellerspeicher ([[Kellerautomat|Kellerautomaten]]) entsprechen [[kontextfreie Sprachen|kontextfreien Sprachen]];
* Akzeptoren mit linear beschränktem Speicher ([[Linear Beschränkte Automaten]]) entsprechen [[kontextsensitive Sprachen|kontextsensitiven Sprachen]];
* [[Turing-Maschine|Turing-Maschinen]] charakterisieren die allgemeinsten mit endlichen Mitteln erzeugbaren formalen Sprachen, die aufzählbaren (oder Typ-0-)Sprachen.

{{wb}}
[[Category:Computerlinguistik]]

← Older revision		Revision as of 17:53, 18 June 2014
Line 1:		Line 1:
		+	{{ref}}
		+
	Die '''Automatentheorie''' befasst sich mit der formalen mathematischen Beschreibung und Untersuchung von [[Automaten]], d.h. von Modellen diskreter sequentieller informationsverarbeitender Systeme.		Die '''Automatentheorie''' befasst sich mit der formalen mathematischen Beschreibung und Untersuchung von [[Automaten]], d.h. von Modellen diskreter sequentieller informationsverarbeitender Systeme.

@@ Line 1: / Line 1: @@
-== Ursprung ==
+Die '''Automatentheorie''' befasst sich mit der formalen mathematischen Beschreibung und Untersuchung von [[Automaten]], d.h. von Modellen diskreter sequentieller informationsverarbeitender Systeme.
-*''griech. automatos'' - sich von selbst bewegend
-== Definition ==
+Die Automatentheorie befasst sich weniger mit der internen Struktur als mit dem Verhalten solcher Systeme; dies wird wiederum darauf reduziert, welche Folgen von Eingaben in das System welche Ausgaben erzeugen können. Bei unendlichen (wachsenden) Automaten spielt jedoch auch die Art und Weise des Wachstums eine wichtige Rolle. Bei Automaten mit potentiell unendlichem Speicher ist die Art des Speicherzugriffs und die Folge der Speicherinhalte wichtig.
 Oft werden akzeptierende Automaten ([[Akzeptor]]) betrachtet, bei denen nur ihre akzeptierte Wortmenge interessiert, d.h. die Menge endlicher Eingabefolgen (Wörter), die den Automat von einem (oder mehreren) Anfangszuständen in einen von (im allgemeinen) mehreren Endzuständen überführen; die Ausgabe besteht also jeweils nur aus einem ''Ja'' oder ''Nein'' nach Ende der Eingabe. Symmetrisch dazu werden auch erzeugende Automaten ([[Generator]]) betrachtet.
 Ferner behandelt man nicht nur [[deterministisch]] arbeitende Automaten (bei denen die Änderung des jeweiligen Zustands und die jeweilige Ausgabe funktional nur von der momentanen Eingabe und dem aktuellen Zustand abhängt), sondern auch [[Nicht-Determinismus|nicht-deterministische Automaten]], bei denen Relationen anstelle von Funktionen die mögliche Arbeitsweise beschreiben.
@@ Line 13: / Line 13: @@
 * Akzeptoren mit linear beschränktem Speicher ([[Linear Beschränkte Automaten]]) entsprechen [[kontextsensitive Sprachen|kontextsensitiven Sprachen]];
 * [[Turing-Maschine|Turing-Maschinen]] charakterisieren die allgemeinsten mit endlichen Mitteln erzeugbaren formalen Sprachen, die aufzählbaren (oder Typ-0-)Sprachen.
 {{wb}}
 [[Category:Computerlinguistik]]