0 Daumen
254 Aufrufe

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.

von

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

1 Antwort

0 Daumen

Konstruiere einen DFA mit Zustandsmenge Q1 für |w|_ca≥1 und einen DFA mit Zustandsmenge Q2 für |w|_b=1 mod 3.

Zustandsmenge des gesuchten Automaten ist Q1 × Q2. 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.

von 3,5 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community