Gegeben ist folgender deterministischer endliche Automat:

´A = ({a, b, c}, {z_0, z_1, z_2, z_3, z_4}, z_0, {z_0}, delta)´

Dabei ist die Überführungsfunktion ´delta´ folgende Tabelle beschrieben:

´delta´ ´z_0´ ´z_1´ ´z_2´ ´z_3´ ´z_4´
´a´ ´z_1´ ´z_3´ ´z_0´ ´z_4´ ´z_3´
´b´ ´z_2´ ´z_0´ ´z_4´ ´z_4´ ´z_3´
´c´ ´z_2´ ´z_0´ ´z_4´ ´z_4´ ´z_3´
  1. Zeichne das Transitionsdiagramm (den Überführungsgraphen) des Automaten A.
  2. Welche der Wörter ´lambda´, ´abab´, ´ababa´, ´caaa´ werden vom Automaten akzeptiert, welche nicht?
  3. Gib die von ´A´ akzeptierte Sprache ´T(A)´ an.
Approach

  1. …

  2. Man entnimmt dem Transitionsgraphen (bzw. erhält durch Rechnung):

    ´delta^(**)(z_0, lambda) = z_0´ ´delta^(**) (z_0, abab) = z_0´ ´delta^(**) (z_0, ababa) = z_1´ ´delta^(**) (z_0, caaa) = z_2´

    Damit werden nur ´lambda´ und ´abab´ akzeptiert.

  3. Man entnimmt dem Transitionsdiagramm sofort, dass nur folgende Wege vom Anfangszustand ´z_0´ zum einzigen akzeptierenden Zustand ´z_0´ führen, ohne dazwischen ´z_0´ zu berühren: ´ab, ac, ba, ca´ Durch beliebig oftmalige Kombination dieser Wörter in beliebiger Reihenfolge ergibt sich die akzeptierte Sprache, d.h. es gilt: ´T(A) = {w_1 w_2 … w_n | n >= 1, w_i in {ab, ac, ba, ca} " für " 1 <= i <= n} uu {lambda}´


Solutions

    1. -> [z0] -- b,c --> z2 [z0] -- a --> z1 z1 -- b,c --> [z0] z1 -- a --> z3 z3 -- a,b,c --> z4 z4 -- a,b,c --> z3 z2 -- b,c --> z4 z2 -- a --> [z0]

    2. ´lambda´ und ´abab´.

    3. ´T(A) = {w_1 w_2 … w_n | n >= 1, w_i in {ab, ac, ba, ca} " für " 1 <= i <= n} uu {lambda}´

  • Teil 3: ´T(A) = {w | w in {ab, ac, ba, ca}^**}´

  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Draw
  • Duration: 40min
  • Credits: 6
  • Difficulty: 0.6
  • Tags: hpi deterministic finite automaton
  • Note:
    HPI, 2014-04-12, Theoretische Informatik 2, Blatt 2, Aufgabe 1
  • Created By: adius
  • Created At:
    2014-07-21 14:19:51 UTC
  • Last Modified:
    2014-07-24 20:50:58 UTC