KAPITEL 1 +2 FORMALE SPRACHEN / Deterministischer endlicher Automat)

Question 1

Definition 1.1 (Alphabet)

Answer 1

Ein Alphabet ist eine endliche Menge von Zeichen

Question 2

Definition 1.2 (Wort)

Answer 2

Ein Wort ¨uber einem Alphabet ist eine endliche Zeichenfolge, die aus keinem oder endlich vielen Zeichen des Alphabets zusammengesetzt ist. Die Zeichen werden unmittelbar hintereinander geschrieben.

Question 3

endliche Automaten

Answer 3

• sehr einfaches Berechnungsmodell

- In Abhängigkeit von einer Eingabe werden gewisse Fallunterscheidungen vorgenommen und unterschiedlich bearbeitet

Question 4

Mealy-Automaten und Moore-Automaten

Answer 4

• endliche Automaten, die taktweise eine auf einem Eingabeband befindliche Eingabe verarbeiten und auf einem Ausgabeband
  eine Ausgabe erzeugen

Question 5

Komponenten Deterministischer endlicher Automat)

Answer 5

Q ist eine endliche nicht-leere Menge, die Zustandsmenge
• Σ ist ein Alphabet, das Eingabealphabet
• δ : Q × Σ → Q ist eine Funktion, die Zustands¨uberf¨uhrungsfunktion oder
auch ¨ Uberf¨uhrungsfunktion
• q0 ∈ Q ist der Startzustand
• F ⊆ Q ist die Menge der Endzust¨ande oder der akzeptierenden Zust¨ande

Question 6

deterministische Variante eines endlichen Automaten

Answer 6

Automaten, f¨ur die zu einem Paar aus Eingabezeichen und Zustand genau ein Folgezustand definiert ist.

Question 7

Defintion Berechnung eine DEA

Answer 7

1. Der erste Zustand r0 muss gleich der Startzustand q0 sein
2. Aus einem zustand r0, kommt man mit einem Eingabezeichen x in den Zustand r0+1
3. Der letzte Zustand rn muss element der Endzustandsmenge F sein

Question 8

Zustandsüberführungstabelle

Answer 8

• Eine solche Uberführungstabelle besteht aus endlich vielen Zeilen.
• Für jedes Argumentpaar (q, x) ∈ Q × Σ von δ muss genau eine Zeile in der Tabelle enthalten sein.
• Dem Startzustand wird ein Pfeil (→) vorangestellt, den Endzust¨anden ein Stern (∗).
• kann auch in Form einer Matrix angeordnet werden
• Die jeweiligen Folgezuständde befinden sich dann als Matrixelemente an den Schnittlinien

Question 9

Bestandteile DEA (5 tupel)

Answer 9

1. Q, eine endliche nicht leere menge, Zustanssmenge
2. Sigma E, Eingabe - Alphabet
3. delta d, Zustandsüberführungsfunktion
4. q element Q, Startzustand
5. F teilmenge von Q, der Endzustände oder akzeptierende Zustände

Question 10

Unterschied bei den Kompononten zwischen DEA und NEA

Answer 10

Die Überführungsfunktion

In DEA: Exakte Bestimmung des Folgezustands nach Worteingabe
In NEA: Folgezustand stammt aus einer Menge, und ist nicht exakt bestimmt

Question 11

nichtdeterministischer endlicher Automat (NEA)

Answer 11

lässt je Zustand und gelesenem Zeichen keinen bis mehrere Folgezustände zu.

Des weiteren kann es auch Zustandsuberführungen geben, ohne dass ein Zeichen des Eingabebandes gelesen wird

Question 12

Äquivalenz von endlichen Automaten

Answer 12

Zwei endliche Automaten sollen als äquivalent bezeichnet werden, wenn die von ihnen erkannten Sprachen gleich sind.

Question 13

Teilmengen-Konstruktion

Answer 13

Sei NEA, dann gibt es dazu einen DEA

Question 14

Definition Reguläre Sprachen

Answer 14

Wenn ein endlicher Automat diese Sprache erkennt