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:\n\n´L\(0,1)^3 = L\(0,2)^2 (L\(2,2)^2)^(\\) L\(2,1)^2 uu L\(0,1)^2´\n\nDa 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\n\n´L\(0,1)^3 = L\(0,1)^2´\n´= L\(0,1)^1 (L\(1,1)^1)^(\\) L\(1,1)^1 uu L\(0,1)^1´\n´= (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)´\n´= ({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})´\n´= ({a} uu {a})({a, b, lambda})^(\\) {a, b, lambda} uu ({a} uu {a})´\n´= {a}({a, b, lambda})^(\\) {a, b, lambda} uu {a}´\n\nDaraus resultiert folgender regulärer Ausdruck:\n\n´(((a \* ((a+b)+ lambda)^(\\)) \* ((a+b) + lambda)^(\\)) + a)´\n\nEin ä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