0 Daumen
70 Aufrufe

Aufgabe:

(Nicht-) Regularität und Klassen

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

von

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 (?)

1 Antwort

0 Daumen

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

Welche Äquivalenzklassen meinst du bei b)?

von 1,7 k  –  ❤ Bedanken per Paypal

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...