DFA / NFA - Problem

edmolf
Erstie
Erstie
Beiträge: 19
Registriert: 15. Okt 2010 13:35

DFA / NFA - Problem

Beitrag von edmolf »

Moin@all!
Ich habe eine Frage zu DFA / NFA vielleicht kann mir ja hier jemand helfen! Ich komme hier auf keine Lösung... :x


Sei Σ := {a,b,c}. Konstruieren Sie endliche Automaten, welche die folgenden Sprachen erkennt:
1.) Ein deterministischen Automaten für L_1:={w = a_i…a_n∈Σ^*:a_i∈{a,b}für gerade i und a_i∈{b,c}für alle durch 3 teilbare i}

2.) Einen minimalen deterministischen Automaten für L_2:= L((a+b+c)^*aaaba(a+b+c)^*) - beweisen sie das dieser Automat minimal ist.

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: DFA / NFA - Problem

Beitrag von dschneid »

Ein paar Ideen:

Zu 1.): Erstmal kannst du die Sprache in den Schnitt zweier einfacherer Sprachen aufteilen, nämlich \(L_{1,1} = \{a_1 ... a_n \in \Sigma^* : a_i \in \{ a, b \} \text{für gerade } i \}\) und \(L_{1,2} = \{a_1 ... a_n \in \Sigma^* : a_i \in \{ b, c \} \text{für durch 3 teilbare } i \}\). Ob nun der gerade gelesene Buchstabe an einer durch 2 bzw. durch 3 teilbaren Position steht, lässt sich mit Automaten erkennen, die unabhängig von der Eingabe einen Zyklus aus 2 bzw. 3 Zuständen durchlaufen. Die Zustände kodieren dann jeweils die Restklassen der Position des letzten gelesenen Buchstabens modulo 2 bzw. 3, ähnlich wie beim Automaten, der beispielsweise genau die Wörter mit einer geraden Anzahl a erkennt. Diese Automaten kannst du so verändern, dass die Transitionen vom jeweils vorherigen Zustand nur noch in die relevanten Nachfolgezustände überführen, wenn die Buchstaben die richtigen sind; ansonsten schickst du die Automaten von dort in einen nicht akzeptierenden Fehlerzustand, aus dem es nicht mehr herausgeht. Alle anderen Zustände sind akzeptierend. Die beiden Automaten kannst du dann mit der Produktautomatenkonstruktion zusammenführen, um einen DFA für die gesamte Sprache zu erhalten.

Zu 2.): Du baust einen beliebigen Automaten (ein NFA dürfte am einfachsten sein) aus dem Regex (das ist ohnehin eine gute Übung für die Klausur). Den kannst du dann determinisieren (Potenzmengenkonstruktion) und minimieren (Äquivalenzklassenkonstruktion). Die Minimalität folgt dann direkt aus der Korrektheit des Minimierungsalgorithmus. Vielleicht findest du auch direkt einen DFA, dann musst du nur minimieren. Dieser Ansatz ist meiner Erfahrung nach schneller als mit hartem Nachdenken direkt auf den minimalen DFA kommen zu wollen.

Antworten

Zurück zu „Archiv“