L2: fehlende Beschränkung?

Question

Teil b)

Bei der Sprache L2 müsste es nicht noch eine beschränkung geben, die sicher stellt das u ungleich a und b ungleich v ist?

So wie ich die Lösung verstehe wäre beispielsweise das Wort 0012 korrekt. Allerdings sollen doch keine zwei gleichen Zeichen aufeinander folgen können!

Wo liegt mein Denkfehler?

vielen Dank

 

Answer 1

Hallo,

nein so eine Beschränkung ist nicht nötig, denn \( w = uabv \Rightarrow  a \neq b \) muss für alle ( \( \forall\) ) mögliche u und v gelten.

Das Wort 0012 ist nicht Teil der Sprache, weil die Partition \( u=\varnothing , a=0, b=0, v = 12\) nicht zugelassen ist.

Damit ein Wort Teil der Sprache ist, muss es für alle mögliche Partitionen die Bedingungen erfüllen, dank der Allquantor \(  \forall \).

Grüße

Antonio (Tutor)

 

Comments

Hallo ,

Nehmen wir nocheinmal das Beispiel 0012, wobei u=0, a=0, b=1 und v=2 ist. Warum ist dies nicht möglich?

---

Hallo,

wie Antonio hier schon richtig geschrieben hat, spielt hier der \( \forall \) Quantor die entscheidende Rolle. Die geschilderte Bedingung muss hier nämlich für alle Zerlegungen von u unv v gelten. Eine Zerlegung haben Sie schon genannt, mit u=0, a=0, b=1 und v=2. Hier gibt es auch kein Problem. Aber wie sieht es mit der Zerlegung u=λ, a=0, b=0 und v=12 aus? Sie haben hier alle Bedingungen für u,v,a,b erfüllt (a,b nur einelementig, u,v beliebig aus {0,1,2}^*) nur eben ist hier a=b, was nicht zulässig ist. Somit ist 0012 nihct in L.

Viele Grüße

Friederike Pfeiffer-Bohnen