Wort
Einführung
Ein Wort über einem Alphabet ist eine endliche Folge von Buchstaben aus der Menge Σ des Eingabealphabets. Die Menge der Wörter, die von einem Automaten akzeptiert werden, nennt man die vom Automaten akzeptierte Sprache. Auch das leere Wort (leere Folge von Buchstaben) kann von einem Automaten akzeptiert werden. Es wird in der Regel mit den griechischen Buchstaben ε (Epsilon) oder λ (Lambda) beschrieben.
Ein Wort [math]\displaystyle{ w }[/math] gehört zur Sprache L des Automaten, wenn [math]\displaystyle{ w \in \Sigma^* }[/math] gilt und der Automat nach dem Lesen von [math]\displaystyle{ w }[/math] in einem Endzustand ist.
Beispiel
Die vom Kaffeeautomaten akzeptierte Sprache ist L={KKKK, EE, EKK, KEK, KKE}. Alle anderen Wörter, die über das Eingabealphabet Σ={E,K} gebildet werden können, gehören nicht zu dieser Sprache.