Regularität und Klassen. (Theoretische Informatik)

Question

Aufgabe:

(Nicht-) Regularität und Klassen

Gegeben ist jeweils eine Sprache.
a) L₁ := {a^m | m > 0 ist eine Quadratzahl}. Zeigen Sie, dass L₁ regulär bzw. nicht-regulär ist.
b) L₂ := {aⁿ bⁿ | n ∈ ℕ ∧ n > 0} ist offensichtlich nicht regulär. Geben sie eine (systematische) Beschreibung der Äquivalenzklassen an.

Comments

Informatikfragen besser direkt hier stellen. Nun hast du in beiden Foren ein paar "ähnliche Fragen". Vielleicht findest du einen Anstoss für deine Rechnung, wenn du die Tags präziser wählst. Hast du noch Bearbeitungszeit (?)

Answer 1

L₁ ist nicht regulär. Das kann mit dem Pumping-Lemma gezeigt werden.

Welche Äquivalenzklassen meinst du bei b)?