Teil 1

Wegen ´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.

Teil 2

Wir betrachten die Mengen

1. ´K_1 = {w | w = va " für ein " v in {a,b}^(**)}´
2. ´K_2 = {w | w = uab " für ein " u in {a,b}^(**)}´
3. ´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}^(**)}´

Es 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.

Damit sind K1, K2 und K3 Teilmengen von Äquivalenzklassen.

• Da ´lambda b !in R´, aber ´ab in R´ gelten, sind ´lambda´ und ´a´ in verschiedenen Äquivalenzklassen.
• Da ´abb !in R´, aber ´ab in R´ gelten, sind ´ab´ und ´a´ in verschiedenen Äquivalenzklassen
• Da ´b lambda !in R´, aber ´a b lambda in R´ gelten, sind ´b´ und ´ab´ in verschiedenen Äquivalenzklassen.

Folglich 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.

Teil 3

Wir betrachten die Mengen

1. ´K_1 = {w {:|:} |w| " ist gerade"}´
2. ´K_2 = {w {:|:} |w| " ist ungerade"}´

Sind ´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.

Analog 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.

Teil 4

Wegen ´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.