Pumping Lemma(für reguläre Sprachen) drei Verständnisfragen

Question

Hallo,

ich habe ein paar Verständnisfragen zum Pumping Lemma für reguläre Sprachen :

1. Wieso tauschen wir den Exponenten mit der Pumpingzahl, z.B. bei \( L=\left\{0^{i^{2}} \mid i \in \mathbb{N}\right\} \) wieso tauscht man da das i mit der Pumpingzahl ?

2. Ist die Pumpingzahl p gleich der Anzahl an Zuständen eines endlichen Automatens bzw. was bedeutet die Pumpingzahjl in Bezug auf die Anzahl der Zustände eines endlichen Automatens?

3. Und müssen wir lediglich zeigen, dass eine Aufteilung xy^iz eine der drei Eigenschaften:

1. Die beiden Wörter \( u \) und \( v \) haben zusammen höchstens die Länge \( n \).
2. Das Wort \( v \) ist nicht leer.
3. Für jede natürliche Zahl (mit 0 ) \( i \) ist das Wort \( u v^{i} w \) in der Sprache \( L \), d. h. die Wörter \( u w, u v w, u v v w, u v v v w \) usw. sind alle in der Sprache \( L \).

nicht erfüllt, oder muss man das für alle möglichen Aufteilung von xy^iz zeigen?

Ich bedanke mich für jede Hilfe.

Answer 1

1. Da wird nichts getauscht.

2. Wenn der Automat einen Kreis hat, aus dem ein akzeptierender Zustand erreichbar ist, dann kann dieser Kreis beliebig häufig durchlaufen werden bevor zum akzeptierenden Zustand abgezweigt wird. Eine geeignete Pumpingzahl ergibt sich aus der Länge des Pfades, der in den Kreis hineinführt plus Länge des Kreises.

Wenn der Automat keinen Kreis hat, aus dem ein akzeptierender Zustand erreichbar ist, dann ist die Sprache endlich und somit regulär.

3. Der übliche Weg ist, für jede natürliche Zahl ein Wort zu konstruieren, so dass jede Aufteilung des Wortes, die 1. und 2. erfüllt, 3. nicht erfüllt.