0 Daumen
931 Aufrufe

Aufgabe:

Gegeben seien zwei DFAs M1 = (Q1, Σ, δ1, q1,F1) und M2 = (Q2, Σ, δ2, q2,F2) über demselben Alphabet Σ.

Konstruieren Sie einen DFA, der die Sprache L(M1) ∪ L(M2) entscheidet.


Ansatz/Problem:

Damit ich den DFA Konstruieren kann, brauche ich die Sprache und die Sprache ist L ⊆ Σ. Das problem ist, dass ich Σ nicht habe.

Avatar von

1 Antwort

+2 Daumen
damit ich den DFA Konstruieren kann brauche ich die Sprache .

Das ist richtig.

Die Sprache ist L(M1) ∪ L(M2).

und die Sprache ist L ⊆ Σ

Aber die Sprache ist nicht ein beliebiges L⊆ Σ, sondern L = L(M1) ∪ L(M2).

Nebenbei, die Sprache ist ein L ⊆ Σ*. L ⊆ Σ würde bedeuten, die Sprache ist eine Menge von Buchstaben. Die Sprache ist aber eine Menge von Wörtern. Die Menge aller Wörter mit Buchstaben aus Σ ist Σ*.

das problem ist ,dass ich  Σ nicht habe.

Das ist kein Problem.

wie kann ich denn mit der lösung anfangen ??

Konstruiere zunächst einen NFA. Ich hoffe du weißt, dass mittels Potenzmengenkonstruktion jeder NFA äquivalent zu einem DFA ist.

uber demselben Alphabet Σ

Das kingt zunächst wie eine Vereinfachung, macht es aber in Wirklichkeit schwieriger. Wenn die Alphabete disjunkt wären, dann könntest du sofort anhand des ersten Zeichens erkennen, in welchen Teilautomaten du verzweigen musst.

Tipp: Gehe zunächst davon aus, das die Alphabete (und Zustandmengen) disjunkt sind und repariere dann die Probleme, die durch diese Annahme entstanden sind.

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community