0 Daumen
316 Aufrufe

Gegeben sei die Sprache \( L=\left\{\$\left(a^{n} b^{n}\right)^{n} \mid n \in \mathrm{N}\right\} \).
Beweisen oder widerlegen Sie: \( L \) ist eine kontextfreie Sprache.

Was wären die Fälle für vwx bei dieser Sprache ?

Avatar von

1 Antwort

0 Daumen

Sei \(p\) die Pumpingzahl.

Wähle zunächst ein Wort aus \(L\).

Erst dann ist es sinnvoll, zu untersuchen, welche Fälle für \(vwx\) auftreten können.

Avatar von 5,7 k

Wenn ich jetzt z.B. z = $(a^nb^n)^n als Wort wähle, dann hat es die Mindestlänge n und vwx kann maximal n groß sein. Die Fälle die ich in diesem Fall erkannt habe, waren, dass vwx ein $ enthält und dann eben maximal nur as enthalten kann. Wenn wir dann z0 wählen hat das Wort kein $ Zeichen mehr und weniger as als bs, weshalb es in diesem Fall nicht mehr in der Sprache wäre. Ein anderer Fall wäre wenn vwx kein Dollar enthält, dann kann es as und bs enthalten, wobei dann z mit z0 nicht mehr in der Sprache liegen würde, da (2*n-i+j)(2n)^(n-1) ungleich (2n)^n(mit i + j >= 1, da vx nicht leer sein darf). Das ist jetzt zwar formal nicht sauber aufgeschrieben, aber das sind eben die Fälle die mir eingefallen sind, geht das in die richtige Richtung bzw. wie könnte man vwx noch wählen ?

wobei vwx kann auch nur as und auch nur bs enthalten, das würde aber dann auch wieder mit z0 zu (2*n-i+j) mit i+j >= 1 führen.

ich meinte natürlich z = $(a^n b^n)^n

Wenn ich jetzt z.B. z = $(anbn)n als Wort wähle,

Wo kommt das n her?

Das ist bei uns die pumpingzahl

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community