Einen NFA entwerfen, der die selbe Sprache wie L akzeptiert.

Question

Aufgabe:

Geben Sie einen NFA mit maximal 15 Zuständen an, der die Sprache L = {a^n | n ≥ 1 und 105 teilt nicht n}
akzeptiert.

Hinweis: 105 = 3 · 5 · 7 und 15 = 3 + 5 + 7.

Problem/Ansatz:

leider habe ich noch keinen Ansatz. Mir währe sehr geholfen, wenn ich Ansätze oder weitere Hinweise von euch bekommen würde.

MfG

Comments

Hi, sind vermutlich beim selbem Kurs,selbe Uni dies das. blabla.

Hab das jetzt auf jeden fall so dargestellt. Und bitte nimm das nicht als ansatzweise als korrekte Lösung an,(weil könnte völliger Bullshit sein was Ich hier erzähl), danke.

Es sind schonmal weniger als 15 Zustände verlangt, also würd die die Aufgabe vermutlich nicht mit viel weniger Zuständen zu lösen sein.

Ich hab das jetzt einfach simple as possible gemacht, einen NFA, der alle alle a^n [heißt aaaa = a^4 etc.] aktzeptiert außer die die, die 105 teilen.

Dank der aufgabenstellung wissen wir, dass wir keine a^3, a^5, a^,7 benutzen können. Daraus jetzt nen nen NFA zu formen sollte meiner meinung nach relativ einfach von statten gehen, indem wir diese Pfade/Läufe als nicht aktzeptierend einordnen, quasi einen nicht aktzeptierenden Zustand für jene Eingaben erzeugen.

Ich kann dir leider keine vorgefertigte Lösung liefern, weil Ich mir mit meiner viel zu unsicher bin...

Jedenfalls hab Ich das so verstanden.

LG und viel Glück.

Answer 1

Der DFA (Q, Σ, δ, q₀ ,F) mit

        Q = {q₀, q₁, q₂}

        Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

        F = {q₁, q₂}

und

         δ(q_i, 0) = δ(q_i, 3) = δ(q_i, 6) = δ(q_i,9) = q_i ∀i∈{0, 1, 2}

        δ(q_i, 1) = δ(q_i, 4) = δ(q_i, 7) = q_(i+1)%3 ∀i∈{0, 1, 2}

        δ(q_i, 2) = δ(q_i, 5) = δ(q_i, 8) = q_(i+2)%3 ∀i∈{0, 1, 2}

erkennt die Zahlen, die durch 3 teilbar sind.

Auf ähnliche Weise kann man DFAs konstruieren, die die Zahlen erkennen, die nicht durch 5 bzw. nicht durch 7 teilbar sind.

Diese drei DFAs können zu einem NFA zusammengesetzt werden, der die Zahlen erkennt, die nicht durch 105 teilbar sind.