Theoretische Informatik - Aufgaben

Aufgabe:  

1. Sei L die Sprache aller Wörter über dem Alphabet A = {a, b}, die aus gleich vielen a's und b's bestehen, d.h.

   L  =  { w ∈ {a, b}*  |  |w|_a = |w|_b }

   Die Notation |w|_a bezeichnet die Anzahl der a's im Wort x.

   Zeigen Sie durch Anwendung des Pumping-Lemmas: L ist nicht regulär.

    

2. Sei L die Sprache der Palindrome¹) gerader Länge über dem Alphabet A = {a, b}, d.h.

   L  =  { ww^R  |  w ∈ {a, b}*,  w^R ist das Spiegelbild von w }

   Zeigen Sie durch Anwendung des Pumping-Lemmas: L ist nicht regulär.

    

3. Zeigen Sie mithilfe des Pumping-Lemmas: Die Sprache L über dem Alphabet A = {a, b} mit

   L  =  { a^mbⁿ  |  m, n ∈ ℕ,  m < n }

   ist nicht regulär.

    

4. Zeigen Sie mithilfe des Pumping-Lemmas: Die Sprache L über dem Alphabet A = {a, b} mit

   L  =  { a^mbⁿ  |  m, n ∈ ℕ,  m > n }

   ist nicht regulär.

    

5. Mit dem Pumping-Lemma lässt sich direkt nicht zeigen: Die Sprache L über dem Alphabet A = {a, b} mit

   L  =  { a^mbⁿ  |  m, n ∈ ℕ,  m ≠ n }

   ist nicht regulär. Zeigen Sie auf andere Weise, dass L nicht regulär ist.