Beschreibung
Die automatische Gruppe ist eine Gruppe über einem Erzeugendensystem, das durch einen Automat beschrieben werden kann.
Definition
Sei eine Gruppe, erzeugt durch , interpretiert als Alphabet einer Sprache. Eine Sprache über dem Alphabet wird eine automatische Struktur für genannt, wenn folgende zwei Bedingungen erfüllt sind:
- ist regulär, d.h. es gibt einen Automat (genannt Wortakzeptierer (word acceptor)), der feststellen kann, ob ein Wort enthalten ist oder nicht.
- über erfüllt die Reisegefährteneigenschaft
Die Gruppe wird automatisch genannt, wenn eine automatische Struktur existiert.
Eigenschaften
Satz: