Theoretische Informatik: Pumping Lemma

30.05.2015, 14:36	credibil	Auf diesen Beitrag antworten »
Theoretische Informatik: Pumping Lemma Hallo zusammen, ich habe eine Frage zur Zerlegung eines Wortes beim Pumping-Lemma: Nehmen wir mal das Standard-Beispiel: $\begin{eqnarray} L= { x \in {a,b} : x=a^nb^n } \end{eqnarray}$ Wir nehmen an, L sei regulär, und wählen n > 0 wie im Pumping Lemma. Im Widerspruch zum Pumping Lemma zeigen wir nun, dass es zu diesem n ein Wort der Länge mindestens n gibt, das nicht gepumpt werden kann. Es sei $\begin{eqnarray} x = uvw \end{eqnarray}$ eine Zerlegung von x mit $\begin{eqnarray} \|uv\| \leq n \end{eqnarray}$ und v ist nicht das leere Wort. Wie kann diese Zerlegung nun aussehen? Gibt es da unterschiedliche Möglichkeiten? In der Lösung zu der Hausübung steht, dass die Zerlegung wie folgt aussehen MUSS: $\begin{eqnarray} u = a^r, v = a^s, w = a^{n-r-s}b^n \end{eqnarray}$ Dieses "muss" verwirrt mich. Warum muss es so sein? Man geht in diesem Fall doch davon aus, dass u und v komplett in a liegen und w den restlichen Teil der a's besitzt und komplett alle b's. Ich könnte doch genau so zeigen, dass $\begin{eqnarray} u = a^{m}, v=a^{n-m} \end{eqnarray}$ und $\begin{eqnarray} w=b^{n} \end{eqnarray}$ ist. Wenn ich dann das v pumpen würde, wäre dementsprechend die Anzahl der a's erhöht und $\begin{eqnarray} a^nb^n \end{eqnarray}$ wäre nicht mehr erfüllt. Wäre dankbar, wenn mir jemand weiterhelfen könnte!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »