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.\nDie Grammatik ergibt sich als\n\n´G = ({z_0, z_1, z_2, z_3}, {a, b, c}, P, z_0)´\n\nmit\n\n´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}´