Gegeben ist der nichtdeterministische endliche Automat

´A = ({a, b}, {q_0, q_1, q_2, q_3}, q_0, {q_3}, delta)´

mit

´delta´ ´q_0´ ´q_1´ ´q_2´ ´q_3´
´a´ ´{q_0, q_1}´ ´{q_2 }´ ´{q_3 }´ ´O/´
´b´ ´{q_0 }´ ´{q_2 }´ ´{q_3}´ ´O/´

  1. Gib für folgende Wörter an, ob sie von ´A´ akzeptiert werden oder nicht:

    1. ´w_1 = lambda´
    2. ´w_2 = "ab"´
    3. ´w_3 = "aab"´
    4. ´w_4 = "baaab"´
    5. ´w_5 = "abbba"´

  2. Gib die von ´A´ akzeptierte Sprache an.

  3. Konstruiere einen deterministischen endlichen Automaten ´A'´, für den ´T(A') = T(A)´ gilt.

Solution

  • Teil 1

    Man errechnet

    ´delta(q_0, w_1) = {q_0}´ ´delta(q_0, w_2) = {q_0, q_2}´ ´delta(q_0, w_3) = {q_0, q_2, q_3}´ ´delta(q_0, w_4) = {q_0, q_2, q_3}´ ´delta(q_0, w_5) = {q_0, q_1}´

    Daraus resultiert, dass nur ´w_3´ und ´w_4´ akzeptiert werden.

    Teil 2

    Wenn beim Lesen von a von ´q_0´ in ´q_1´ gewechselt wird, so wird nach dem Lesen zweier Buchstaben ´q_3´ erreicht, und danach sind keine Übergänge mehr definiert. Ferner ist dies die einzige Möglichkeit, in den einzigen akzeptierenden Zustand ´q_3´ zu gelangen. Daher wird ein Wort nur akzeptiert, wenn an drittletzter Stelle ein ´a´ steht. D.h.

    ´T(A) = {w | w = w'axy " für " w' in {a,b}^(**), x, y in {a,b}}´

    Teil 3

    Der deterministische Automat ´A' = ({a,b}, Z, {z_0}, F', delta')´ benutzt als Zustandsmenge ´Z´ die Teilmengen von ´{q_0, q_1, q_2, q_3}´. Die Menge ´F'´ besteht aus allen Zuständen von ´Z´, die ´q_3´ enthalten. Die Übergänge für Mengen, die ´q_3´ nicht enthalten, sind in folgender Tabelle enthalten:

    ´delta´ ´O/ ´ ´{q_0 }´ ´{q_1 }´ ´{q_2 }´ ´{q_0, q_1}´ ´{q_0, q_2}´ ´{q_1, q_2}´ ´{q_0, q_1, q_2}´
    ´a´ ´O/ ´ ´{q_0, q_1}´ ´{q_2 }´ ´{q_3 }´ ´{q_0, q_1, q_2}´ ´{q_0, q_1, q_3}´ ´{q_2, q_3}´ ´{q_0, q_1, q_2, q_3}´
    ´b´ ´O/ ´ ´{q_0 }´ ´{q_2 }´ ´{q_3 }´ ´{q_0, q_2}´ ´{q_0, q_3}´ ´{q_2, q_3}´ ´{q_0, q_2, q_3}´

    Für eine Menge ´A sube {q_0, q_1, q_2, q_3}´ mit ´q_3 in A´ sei ´A' = A setminus {q_3}´. Dann gilt wegen ´delta(q_3, a) = delta(q_3, b) = O/´ die Beziehung ´delta'(A, x) = delta'(A', x)´.

  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Name
  • Duration: 50min
  • Credits: 9
  • Difficulty: 0.6
  • Tags: hpi nondeterministic finite automaton
  • Note:
    HPI, 2014-04-12, Theoretische Informatik 2, Blatt 2, Aufgabe 3
  • Created By: adius
  • Created At:
    2014-07-21 17:15:22 UTC
  • Last Modified:
    2014-07-24 15:38:12 UTC