DFA aus Sprache konstruieren L={w∈∑*| |w|_ca≥1 und |w|_b=1 mod 3}

Question

Ich habe tausend Ansätze gemacht, um von der Sprache L={w∈∑*| |w|_ca≥1 und |w|_b=1 mod 3} auf einen DFA zu kommen. Dafür ist sowohl der Zustandsgraph als auch eine Übersetzungstabelle für delta zu erstellen.

Mein Plan ist es erst den Graph zu zeichnen, da ja dann die Tabelle einfach daraus abzulesen ist.

Aber wie komme ich auf den Graphen; ich habe das Gefühl er würde aus viel zu vielen Zuständen entstehen.

Immer dann, wenn ich denke, dass ich es habe, finde ich ein Wort, welches nicht vom DFA akzeptiert wird.

Angefangen habe ich mit z_0, von dem aus a, b und c zu jeweils einem Zustand abgehen.

Comments

Was bedeuten |w|_ca und |w|_b?

Answer 1

Konstruiere einen DFA mit Zustandsmenge Q₁ für |w|_ca≥1 und einen DFA mit Zustandsmenge Q₂ für |w|_b=1 mod 3.

Zustandsmenge des gesuchten Automaten ist Q₁ × Q₂. Es gibt eine Transition von (p,q) nach (r,s) mittels eines Buchstaben b, wenn es im ersten DFA eine Transition von p nach r mittels b und im zweiten DFA eine Transition von q nach s mittels b gibt. Akzeptierende Zustände sind die Zustände (p,q), bei denen p im ersten DFA und q im zweiten DFA akzeptierend ist.