Wichtige Begriffe und endliche Automaten
Formale Sprachen sind überall in der Informatik - von Programmiersprachen bis zu Suchmaschinen. Ein Alphabet ist einfach eine Sammlung von Zeichen wiea,b,c, und ein Wort ist eine Folge dieser Zeichen.
Endliche Automaten funktionieren wie intelligente Prüfer: Sie haben verschiedene Zustände und entscheiden, ob ein Wort zu ihrer Sprache gehört oder nicht. Stell dir vor, sie wandern durch ein Labyrinth von Zuständen - kommen sie am Ende an einem Endzustand an, wird das Wort akzeptiert.
Ein Automat besteht aus fünf Komponenten: Zuständen (Q), einem Startzustand (s), dem Eingabealphabet (Σ), Endzuständen (F) und Übergangsfunktionen (δ). Die Übergangsfunktion bestimmt, wohin der Automat bei jedem Zeichen springt.
Merktipp: Automaten sind wie Türsteher - sie lassen nur bestimmte Wörter in den Club (die Sprache) hinein!
Die Grenzen? Endliche Automaten können nicht unendlich zählen - sie haben nur eine begrenzte Anzahl von Zuständen.