logo

Theorie der Automaten

Die Automatentheorie ist ein theoretischer Zweig der Informatik und Mathematik. Es handelt sich um das Studium abstrakter Maschinen und der Rechenprobleme, die mit diesen Maschinen gelöst werden können. Die abstrakte Maschine wird Automaten genannt. Die Hauptmotivation bei der Entwicklung der Automatentheorie bestand darin, Methoden zur Beschreibung und Analyse des dynamischen Verhaltens diskreter Systeme zu entwickeln.

Dieser Automat besteht aus Zuständen und Übergängen. Der Zustand wird vertreten durch Kreise , und das Übergänge wird vertreten durch Pfeile .

Automaten sind die Art von Maschine, die eine Zeichenfolge als Eingabe erhält und diese Eingabe eine endliche Anzahl von Zuständen durchläuft und in den Endzustand eintreten kann.

Es gibt die grundlegenden Terminologien, die wichtig sind und in Automaten häufig verwendet werden:

Symbole:

Symbole sind eine Einheit oder einzelne Objekte, die ein beliebiger Buchstabe, ein beliebiges Alphabet oder ein beliebiges Bild sein können.

Beispiel:

1, a, b, #

Alphabete:

Alphabete sind eine endliche Menge von Symbolen. Es wird mit ∑ bezeichnet.

Beispiele:

 ∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} 

Zeichenfolge:

Es handelt sich um eine endliche Sammlung von Symbolen aus dem Alphabet. Die Zeichenfolge wird mit w bezeichnet.

Beispiel 1:

Wenn ∑ = {a, b}, sind verschiedene Zeichenfolgen, die aus ∑ generiert werden können, {ab, aa, aaa, bb, bbb, ba, aba.....}.

  • Eine Zeichenfolge mit null Vorkommen von Symbolen wird als leere Zeichenfolge bezeichnet. Es wird durch ε dargestellt.
  • Die Anzahl der Symbole in einer Zeichenfolge w wird als Länge einer Zeichenfolge bezeichnet. Es wird mit |w| bezeichnet.

Beispiel 2:

 w = 010 Number of Sting |w| = 3 

Sprache:

Eine Sprache ist eine Sammlung geeigneter Zeichenfolgen. Eine Sprache, die über Σ gebildet wird, kann sein Endlich oder Unendlich .

Beispiel 1

 L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> 

Beispiel: 2

 L2 = {Set of all strings starts with &apos;a&apos;} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>