Beschreibe Algorithmen, die folgende Probleme entscheiden

Question

Hallo zusammen,

ich stehe grade total auf dem Schlauch, hoffentlich könnt ihr mir etwas weiterhelfen.

Die Aufgabe lautet: Beschreibe Algorithmen, die folgende Probleme entscheiden:

a) L = {A | A ist ein DEA über {0,1}, der das leere Wort nicht akzeptiert}

b) L = {A | A ist ein DEA über {0,1}, der kein Wort mit einer geraden Anzahl Nullen akzeptiert}

c) L = {phi | phi ist eine erfüllbare aussagenlogische Formel}

Zu a): Ein DEA akzeptiert doch per Definition bereits kein leeres Wort, oder täusche ich mich? Was für ein Algorithmus ist dann hier gemeint?

Sind hier generell bspw. Wortproblem, Halteproblem etc. gesucht oder soll ich eigene Algorithmen beschreiben?

Danke für eure Hilf

Comments

Du meinst https://de.wikipedia.org/wiki/Deterministischer_endlicher_Automat (Englisch DFA ?) Vielleicht findest du in diesem Link schon selbst eine Antwort.

DEA kann alles mögliche heissen. https://de.wikipedia.org/wiki/Dea

Answer 1

Zu b) . Hier ein DEA (DFA), der nur Wörter mit einer geraden Anzahl Nullen akzeptiert.

https://en.wikipedia.org/wiki/Deterministic_finite_automaton#Example

Das kannst du bestimmt selbst studieren und dann auf die Einsen umbauen und zum Schluss noch negieren.

Zu a)

 Zu a): Ein DEA akzeptiert doch per Definition bereits kein leeres Wort, oder täusche ich mich?

Betrachte den Automaten in meinem englischen Link. Dort ist F = {S1}. Daher akzeptiert der Automat im Link auch das leere Wort.

Wenn man das leere Wort nicht dabei haben will, kann man z.B. fordern, dass F ≠ {q0} . Im verlinkten Beispiel würde man damit aber auch z.B. das Wort 111 ausschliessen. Man könnte selbstverständlich die Übergangstabelle noch umbauen.

Deine Frage, was mit "beschreiben" gemeint ist, kann hoffentlich jemand anders beantworten. Am ehesten wohl  die Quelle aus der du die Frage hast.

Mathematisch ist eine Definition eine Beschreibung. Du kannst aber auch in ein / zwei Sätzen hinschreiben, wie eine Definition auszusehen hat. Dann hast du auch die umgangssprachliche Bedeutung von beschreiben berücksichtigt.