Bestimme nach der im Beweis des Satzes von Kleene gegebenen Methode zu folgendem endlichen Automaten einen regulären Ausdruck ´R´ mit ´M(R) = T(A)´:
´A = ({a, b}, {0, 1, 2}, 0, {1}, delta)´
mit
´delta(0,a) = 1´ ´delta(1,a) = 1´ ´delta(2,a) = 2´ ´delta(0,b) = 2´ ´delta(1,b) = 1´ ´delta(2,b) = 2´
Man muss ´L_(0,1)^3´ bestimmen. Man erhält zuerst:
´L_(0,1)^3 = L_(0,2)^2 (L_(2,2)^2)^(**) L_(2,1)^2 uu L_(0,1)^2´
Da der Zustand ´2´ nicht verlassen werden kann, ist offenbar ´L_(2,1)^2´ leer. Somit gilt ´L_(0,1)^3 = L_(0,1)^2´. Dadurch ergibt sich
´L_(0,1)^3 = L_(0,1)^2´ ´= L_(0,1)^1 (L_(1,1)^1)^(**) L_(1,1)^1 uu L_(0,1)^1´ ´= (L_(0,0)^0 (L_(0,0)^0)^(**) L_(0,1)^0 uu L_(0,1)^0) (L_(1,0)^0 (L_(0,0)^0)^(**) L_(0,1)^0 uu L_(1,1)^0)^(**) ´´(L_(1,0)^0 (L_(0,0)^0)^(**) L_(0,1)^0 uu L_(1,1)^0) uu (L_(0,0)^0 (L_(0,0)^0)^(**) L_(0,1)^0 uu L_(0,1)^0)´ ´= ({lambda}{lambda}^(**) {a} uu {a})(O/ {lambda}^(**) {a} uu {a, b, lambda})^(**)´´(O/ {lambda}^(**) {a} uu {a, b, lambda}) uu ({lambda} {lambda}^(**) {a} uu {a})´ ´= ({a} uu {a})({a, b, lambda})^(**) {a, b, lambda} uu ({a} uu {a})´ ´= {a}({a, b, lambda})^(**) {a, b, lambda} uu {a}´
Daraus resultiert folgender regulärer Ausdruck:
´(((a * ((a+b)+ lambda)^(**)) * ((a+b) + lambda)^(**)) + a)´
Ein äquivalenter Ausdruck ist offensichtlich ´(a * (a + b)^(**))´.
´(((a * ((a+b)+ lambda)^(**)) * ((a+b) + lambda)^(**)) + a)´
´(a * (a + b)^(**))´
HPI, 2014-05-13, Theoretische Informatik 2, Blatt 6, Aufgabe 2
2014-07-22 16:46:59 UTC
2014-07-22 16:46:59 UTC