L1 ist regulär.
Angenommen L2 ist regulär.
Sei n ∈ ℕ, so dass sich jedes Wort w ∈ L1 mit |w| ≥ n so in w=pqr zerlegen lässt, dass |q| ≥ 1 und |pq| ≤ n und pqkr ∈ L2 für jedes k ∈ ℕ ist. (Kurz gesagt, sei n die Pumping-Zahl).
Sei w = ancbn. Dann ist w ∈ L2.
Für jede Zerlegung w = pqr von w, mit |q| ≥ 1 und |pq| ≤ n ist q = am für ein m ∈ ℕ. Laut Pumping Lemma gibt es also ein m ≥ 1, so dass an-ma2mcbn ∈ L2 ist. Das ist ein Widerspruch zur Definition von L2.
Zu L1: Sei w in {a,b}*
Sei w = pq.
Fall 1: #a(p) = #b(q). Dann ist w ∈ L1.
Fall 2: #a(p) > #b(q). Entferne den letzten Buchstaben von p und füge ihn an den Anfang von q an.
Fall 2.1: Dieser Buchstabe war ein a. Dann ist #a(p) um 1 gesunken und #b(q) ist gleichgeblieben.
Fall 2.2: Dieser Buchstabe war ein b. Dann ist #a(p) gleich geblieben und #b(q) um 1 gestiegen.
Fall 3: #a(p) < #b(q). Entferne den ersten Buchstaben von q und füge ihn an das Ende von p.
Fall 3.1: Dieser Buchstabe war ein a. Dann ist #a(p) um 1 gestiegen und #b(q) ist gleichgeblieben.
Fall 3.2: Dieser Buchstabe war ein b. Dann ist #a(p) gleichgeblieben und #b(q) um 1 gesunken.
Wiederhole mit den neuen p und q bis du entweder am Rand des Wortes angekommen bist oder im Fall 1 gelandet bist.
Wie sehen die Wörter aus, bei denen du am Rand des Wortes ankommst?
Wenn du das mal mit w = abaabaaabbaaaabaaaaa und p = abaabaaabb, q = aaaabaaaaa durchspielst, dann wirst du feststellen, dass w ∈ L1 ist.