Gegeben sei folgender endlicher Automat:

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

mit

´delta´ | ´z_0´ | ´z_1´ | ´z_2´ | ´z_3´ ---|---|---|--- ´a´ | ´z_1´ | ´z_2´ | ´z_2´ | ´z_1´ ´b´ | ´z_3´ | ´z_3´ | ´z_2´ | ´z_3´ ´c´ | ´z_1´ | ´z_1´ | ´z_2´ | ´z_1´

Gib eine reguläre Grammatik an, die ´T(A)´ erzeugt.

Approach

Wir haben für jede Überführung ´delta(z, x) = z'´ eine Regel ´z -> xz'´ und für jeden Zustand ´z in F´ eine Regel ´z -> lambda´ aufzunehmen. Die Grammatik ergibt sich als

´G = ({z_0, z_1, z_2, z_3}, {a, b, c}, P, z_0)´

mit

´P = {z_0 -> a z_1, z_0 -> b z_3, ´´z_0 -> c z_1, z_1 -> a z_2, ´´z_1 -> b z_3, z_1 -> c z_1, ´´z_2 -> a z_2, z_2 -> b z_2, ´´z_2 -> c z_2, z_3 -> a z_1, ´´z_3 -> b z_3, z_3 -> c z_1, ´´z_2 -> lambda}´


Solution

  • ´G = ({z_0, z_1, z_2, z_3}, {a, b, c}, P, z_0)´

    mit

    ´P = {z_0 -> a z_1, z_0 -> b z_3, ´´z_0 -> c z_1, z_1 -> a z_2, ´´z_1 -> b z_3, z_1 -> c z_1, ´´z_2 -> a z_2, z_2 -> b z_2, ´´z_2 -> c z_2, z_3 -> a z_1, ´´z_3 -> b z_3, z_3 -> c z_1, ´´z_2 -> lambda}´

  • URL:
  • Language:
  • Subjects: theoretical computer science
  • Type: Name
  • Duration: 35min
  • Credits: 4
  • Difficulty: 0.5
  • Tags: hpi finite automaton regular grammar
  • Note:
    HPI, 2014-04-12, Theoretische Informatik 2, Blatt 2, Aufgabe 5
  • Created By: adius
  • Created At:
    2014-07-21 18:28:32 UTC
  • Last Modified:
    2014-07-21 18:28:32 UTC