Einführung

Question 1

DFA - Definition

Answer 1

Question 2

delta-hut Funktion für DFA - Definiton

Answer 2

Question 3

DFA - akzeptieren eines Wortes

Answer 3

Question 4

DFA - Beispielautomat

Answer 4

Question 5

DFA - Zustandsgraph

Answer 5

Question 6

Gibt es einen DFA zur Erkennung folgernder Sprache?

Answer 6

Ja

Letztes Zeichen muss eine 0 sein.

Question 7

Gibt es einen DFA zur Erkennung folgernder Sprache?

Answer 7

Ja

Sprache enthält nur 1001 Wörter. Jede endliche Sprache ist regulär.

Question 8

Gibt es einen DFA zur Erkennung folgernder Sprache?

Answer 8

Nein

Mit endlich vielen Zuständen können wir uns nicht “merken” wieviele a’s wir schon gelesen haben. Erkennung mit Kellerautomat möglich.

Question 9

Gibt es einen DFA zur Erkennung folgernder Sprache?

Answer 9

Ja

Question 10

Gibt es einen DFA zur Erkennung folgernder Sprache?

Answer 10

Ja

Müssen uns nur “merken” welche Buchstaben noch folgen dürfen.

Question 11

Gibt es einen DFA zur Erkennung folgernder Sprache?

Answer 11

Nein

Mit endlcih vielen Zuständen können wir und nicht “merken” wieviele a’s oder b’s wir schon gelesen haben. Erkennung mit Kellerautomaten möglich

Question 12

Gibt es einen DFA zur Erkennung folgernder Sprache?

Answer 12

Nein

Mit endlich vielen Zuständen können wir uns nicht “merken” wieviele a’s oder c’s wir schon glesen haben. Erkennung mit Kellerautomaten möglich.

Question 13

Turing-Maschine - Definition

Answer 13

Question 14

Interpretation von:

Bei einer Turingmaschine

Answer 14

Question 15

Konfiguration einer TM - Definition

Answer 15

“Momentaufnahme” der TM zu einem bestimmten Zeitpunkt bei der Abarbeitung einer Eingabe.

Question 16

Startkonfiguration einer TM - Definiton

Answer 16

Question 17

haltende Konfiguration - Definiton

Bei einer Turing-Maschine

Answer 17

k ist eine Konfiguration einer TM

Question 18

akzeptierende Konfiguration - Definition

Bei einer Turing-Maschien

Answer 18

k ist eine Konfiguration einer TM

Question 19

Mehrer Schritte bei einer Turing-Maschine auf einmal

Answer 19

Question 20

TM - Beispiel

Answer 20

Question 21

TM - Zustandsgraph

Answer 21

Question 22

TM hält auf Wort w - Definition

Answer 22

Question 23

TM akzeptiert Wort w - Definiton

Answer 23

Question 23

M akzeptiert Sprache T(M) - Defintion

Answer 23

Question 24

Abschlusseigenschaften einer TM

Answer 24

Sprachen L und L' werden akzeptiert von TM M und M': * L geschnitten L': kann von einer TM dargestellt werden. * L vereinigt L': kann von einer TM dargestellt werden. * L \ L': kann nicht von einer TM dargestellt werden.