Ist die jeweilige Sprache regulär?

Question

Aufgabe:

Frohes neues Jahr!

leider komme ich mit dieser Aufgabe nicht zurecht und würde mich über jeden Ansatz freuen!

Aufgabe: Geben Sie für folgende Sprachen über dem Alphabet Σ = {a, b} den Index der Rechtskongruenz RL sowie jede Äquivalenzklasse an, falls dieser Index endlich ist. Falls dies nicht der Fall ist, begründen Sie weshalb der Index unendlich ist. Ist die jeweilige Sprache regulär?

1. L1 := {w ∈ Σ* | w enthält die Zeichenkette aba}
2. L2 :={aⁿ b^m | n, m∈N mit n und m gerade}
3. L3 :={aⁿ bⁿ⁺¹ | n∈N}

Answer 1

Lies dir durch was Rechtskongruenz bedeutet.

Lies dir durch was Index der Rechtskongruenz bedeutet.

Lies dir durch was Äquivalenzklassen sind.

Schnapp dir ein Wort \(w\in \Sigma^*\).

Bestimme ein \(w'\in \Sigma^*\), so dass \(ww'\in L_1\) ist.

Bestimme die Menge \(S_w\) aller \(w'\in \Sigma^*\), so dass \(ww'\in L_1\) ist.

Comments

Ich habe bereits Aufgabe 1 und 2 gelöst.

Bei 3. ist der Index unendlich, also ist L3 nicht regulär. Jedoch weiß ich nicht, wie ich das genau beweisen könnte. Hättest du da evtl. einen Ansatz?

LG!

---

Für \(n_1,n_2\in \mathbb{N}\) mit \(n_1 < n_2\) ist \(a^{n_1}a^{n_2-n_1}b^{n_2+1}\in L_3\), aber \(a^{n_2}a^{n_2-n_1}b^{n_2+1}\notin L_3\).

Für \(n_1,n_2\in \mathbb{N}\) mit \(n_1 < n_2\) ist deshalb \(\left[a^{n_1}\right]\neq \left[a^{n_2}\right]\).