Pumping Lemma Proof Strategy

Proving a language is non-regular using the Pumping Lemma involves a specific sequence of logical steps. The process starts with a fundamental assumption and concludes by demonstrating a contradiction.

Correct Order of Pumping Lemma Steps

The standard procedure for applying the Pumping Lemma to show a language $L$ is non-regular follows these steps:

1. B. Assume the language is regular: Begin by hypothesizing that the language $L$ is indeed regular. This is the premise that will be disproven.
2. C. Choose a string of length $\ge$ pumping length: Select a specific string $s$ that belongs to the language $L$, ensuring its length is greater than or equal to the pumping length $p$ (i.e., $|s| \ge p$). The pumping length $p$ is guaranteed to exist if the language is regular.
3. A. Split into xyz satisfying Pumping Lemma conditions: Divide the chosen string $s$ into three non-empty substrings $x$, $y$, and $z$ such that $s = xyz$. These substrings must adhere to the Pumping Lemma conditions: $|xy| \le p$ and $|y| > 0$.
4. D. Show contradiction when pumping y: Pump the substring $y$ by repeating it one or more times (e.g., form strings $xy^iz$ where $i$ is a non-negative integer). Show that for at least one value of $i \ne 1$, the resulting string $xy^iz$ is *not* in the language $L$. This creates a contradiction with the initial assumption that $L$ is regular.

Therefore, the correct execution order is B, C, A, D.