"\nTeil 1\n\nWegen ´a^rca^r in R´ und ´a^sca^r !in R´ für ´r != s´, sind die Wörter ´a^r, r >= 1´, paarweise nicht äquivalent. Folglich haben wir unendlich viele Äquivalenzklassen. Daher ist ´Ind(∼_R)´ nicht endlich, und ´R´ ist nicht regulär nach dem Satz von Myhill/Nerode.\n\n\nTeil 2\n\nWir betrachten die Mengen\n\n1. ´K_1 = {w | w = va " für ein " v in {a,b}^(\\)}´\n2. ´K_2 = {w | w = uab " für ein " u in {a,b}^(\\)}´\n3. ´K_3 = {a,b}^(\\) setminus (K_1 uu K_2) = {lambda, b} uu {w | w = z b b " für ein " z in {a,b}^(\\)}´\n\n\nEs seien ´w_1 = v_1a´ und ´w_2 = v_2a´ zwei Wörter aus ´K_1´. Dann sind ´w_1´, ´w_2´, ´w_1a´ und ´w_2a´ sämtlich nicht in ´R´, während ´w_1b´ und ´w_2b´ beide in ´R´ sind. Folglich gilt für ´x´ der Länge ´<= 1´, dass ´w_1x in R´ genau dann gilt, wenn ´w_2x in R´ gilt. Wenn ´x´ mindestens die Länge ´2´ hat, so enden ´w_1x´ und ´w_2x´ mit dem gleichen Wort der Länge ´2´, also beide auf ´ab´ oder beide nicht auf ´ab´, womit erneut gezeigt ist, dass ´w_1x in R´ genau dann gilt, wenn ´w_2x in R´ gilt. Folglich sind alle Elemente aus ´K_1´ zueinander äquivalent bez. ´∼_R´. Analog beweist mann, dass alle Elemente aus ´K_2´ bzw. ´K_3´ paarweise äquivalent sind.\n\nDamit sind K1, K2 und K3 Teilmengen von Äquivalenzklassen.\n\n- Da ´lambda b !in R´, aber ´ab in R´ gelten, sind ´lambda´ und ´a´ in verschiedenen Äquivalenzklassen.\n- Da ´abb !in R´, aber ´ab in R´ gelten, sind ´ab´ und ´a´ in verschiedenen Äquivalenzklassen\n- Da ´b lambda !in R´, aber ´a b lambda in R´ gelten, sind ´b´ und ´ab´ in verschiedenen Äquivalenzklassen.\n\n\nFolglich sind ´K_1´, ´K_2´ und ´K_3´ die Äquivalenzklassen bez. ´∼_R´. Wegen ´Ind(∼_R) = 3´ ist ´R´ nach dem Satz von Myhill/Nerode regulär.\n\n\n**Teil 3**\n\nWir betrachten die Mengen\n\n1. ´K_1 = {w {:|:} |w| " ist gerade"}´\n2. ´K_2 = {w {:|:} |w| " ist ungerade"}´\n\nSind ´w\_1´ und ´w\_2 in K\_1´, so folgt für ´x´ mit gerader Länge, dass ´w\_1x´ und ´w\_2x´ beide in ´R´ liegen. Hat ´x´ dagegen ungerade Länge, so sind ´w\_1x´ und ´w\_2x´ beide nicht in ´R´. Damit gilt ´w\_1x in R´ genau dann, wenn auch ´w\_2x in R´ gilt. Somit haben wir ´w\_1 ∼\_R w\_2´. Damit ist ´K\_1´ Teilmenge einer Äquivalenzklasse.\n\nAnalog beweist man, dass auch ´K\_2´ in einer Äquivalenzklasse liegt. Wegen ´aa in R´ und ´aaa !in R´ sind aber ´a´ und ´aa´ in verschiedenen Äquivalenzklassen. Da ´K\_1 uu K2 = {a,b}^(\*\*)´ gilt, hat ´∼\_R´ den Index ´2´. Somit ist ´R´ nach Satz von Myhill/Nerode regulär.\n\n\n**Teil 4**\n\nWegen ´a\_rb\_r in R´ und ´a^sb^r !in R´ für ´r != s´, sind die Wörter ´a^r, r >= 1´, paarweise nicht äquivalent. Folglich haben wir unendlich viele Äquivalenzklassen. Daher ist ´Ind(∼\_R)´ nicht endlich, und ´R´ ist nicht regulär nach dem Satz von Myhill/Nerode."