date-created: 2024-06-11 07:38:16 date-modified: 2024-06-11 07:48:48

Pumping-Lemma von Bar-Hillel

anchored to 112.00_anchor_overview proceeds from 112.08_grammatiken and is similar to 112.07_pumping_lemma Tags: #computerscience #complexitytheory

Definition

[!Definition] Kontext-Freie-Grammatiken mit dem Pumping-Lemma beschreiben wie ist es aufgebaut, welche notwendige Betrachtungen und 3 Aspekte müssen eingehalten werden? #card

Sei $G$ eine kontextfreie Grammatik in $CNF$ mit $\mid V\mid =n$ Variablen Dann gilt für jedes $x\in L(G)$ mit $\mid x\mid \ge 2^n$ das es eine Zerlegung $x=r_1{q}_{1}r{q}_2{r}_2$ sodass dann folgende 3 Attribute gelten:

1. $\mid q_1,r{q}_2\mid \le 2^n$
2. $\mid q_1{q}_2\mid >0$
3. $\forall i\ge 0:r_1{q}_1^{i}r{q}_2^i{r}_2\in L(G)$

Wir können also in der Betrachtung eines Baumes einen Weg durch diesen Baum betrachten und werden hier bei wird irgendwann eine Iteration erhalten, die eine Schleife in der Ausführung der Variablen und ihrer Umsetzung “hat” bzw. sich da das Pattern wiederholt.

Nutzen des Pumping Lemmas

Wir können uns exemplarische eine Sprache anschauen und damit zeigen, dass sie nicht kontextfrei ist!

[!Example]

Die Sprache $L=\{a^n{b}^n{c}^n\mid n>0\}$ ist nicht kontextfrei

warum, wie können wir das unter Anwendung des Lemmas zeigen? #card

Sei $L$ Kontextfrei, und werde ferner die CFG $G$ mit in der CNF Chomsky Normalform dargestellt.

Wir wählen jetzt $k$ so, dass $\mid a^k{b}^k{c}^k\mid >2^n,k>2^n/3$ Gemäß des Pumping Lemmas für CFGs gäbe es dann eine Zerlegung $a^k{b}^K{c}^k=r_1{q}_{1}r{q}_2{r}_2.|q_1{q}_2\mid \ge 1,\wedge r_1{q}_1^{i}r{q}_2^i{r}_2\in L,\forall i\ge 0$ Aber das ist ein Widerspruch, weil $q_1{q}_2$ entweder $a\vee b$ enthalten und somit $r\to b\vee c$ enthält und somit die Konstruktion mit $i=2$ nicht in L sein kann. –> Dadurch ist die Sprache $L$ also nicht kontextfrei!

Konzeptuell ist es klar, dass wir hier wieder zeigen können, dass diese Struktur nicht kontextfrei ist. Dafür betrachten wir also eine der Zerteilungen und dann müsste es möglich sein einen solchen Part beliebig wiederholen zu können. Dann würden wir aber die Ordnung von $a,b\vee c$ verlieren.

Anwendung

Folgend ein Beispiel zur Anwendung des Lemmas: