Question

Zeige mittels des Pumping Lemmas für Kontextfreie Spachen, dass L = { a^n ba^m ba^n | m > n} nicht kontextfrei ist.

Für jegliche Hilfe wäre ich dankbar.

Answer 1

Sei \(p \in \mathbb{N}\).

Zeige: für jede Zerstückelung des Wortes \(a^{p-1}ba^pba^{p-1}\) in \(uvwxy\) mit \(|vwx| \leq p\) und \(|vx| \geq 1\) gilt \(uwy \notin L\).