The Formal statement of the pumping lemma for regular languages:

Let $L$ be a regular language. Then there exists an integer $p \ge 1$ depending only on $L$ such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

$|y| \ge 1$;

$|xy| \le p$

for all $i \ge 0$, $x(y^i)z$ $\epsilon L$

If $M$ is a DFA with $k$ states which implements $L$ (which means $L=L(M)$) , can I assume that $p$(from the pumping lemma) is smaller or equal to $k$?

if so ,how to prove this assumption?


You prove this by understanding why the pumping lemma works in the first place. For regular languages, the idea is simple.

First, observe that if you feed $n$ symbols to a DFA, it visits $n+1$ (not necessarily distinct) states - it starts out at the initial state, and each symbol changes the state at most once. You can view this sequence of $n+1$ states as a walk through the DFA's state graph.

Next, check what happens if a state is visited twice while accepting some word $w$, i.e. if the walk through the DFA's state graph contains a loop. Since the state is the only information the DFA has about the past, once it allows you to loop, it allows you to loop arbitrarily often. So what you do is you split $w$ into three parts $xyz$. $x$ leads you from the initial state to some state $q$ which is the starting point of the loop. $y$ leads you around the loop, i.e. starts and ends at state $q$. $z$ takes you from $q$ to some accepting state. Now, if you instead of $xyz$ feed the word $x\underbrace{y\ldots y}_{n\text{ times}}z$ to the DFA, the DFA won't know the difference - $x$ will still lead you to state $q$, then you walk the loop $n$ times, again ending up in state $q$, and finally go from $q$ to an accepting state.

This always works if the walk contains a loop. Now, if a DFA has $k$ states, any walk that visits more than $k$ states must visit some state at least twice, i.e. contain a loop. Since we concluded above that a word of lenght $n$ corresponds to a walk visiting $n+1$ states, if the word is at least $k$ symbols long, it'll at least visit $k+1 > k$ states. So yes, the pumping lemma applies to any word of $k$ symbols or more.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.