Theoretische Informatik - Aufgaben

Anwendung des Pumping-Lemmas

 aufwärts

Die Aufgaben a und b sind auch im Artikel über das Pumping-Lemma gestellt.

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 Element {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 Palindrome1) gerader Länge über dem Alphabet A = {a, b}, d.h.

    L  =  { wwR  |  w Element {a, b}*,  wR 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  =  { ambn  |  m, n Element natürliche Zahlenm<n }

    ist nicht regulär.

     

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

    L  =  { ambn  |  m, n Element natürliche Zahlenm>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  =  { ambn  |  m, n Element natürliche Zahlenm ≠ n }

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

 

 

 

 


1)  Ein Palindrom ist ein Wort, das man vorwärts und rückwärts lesen kann, wie z.B. otto.

 

up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 11.12.2009   Updated: 10.06.2018
Valid HTML 4.01 Transitional