2
$\begingroup$

$$L=\{0^n1^m | (n+m) \text{is even}\}$$

  1. Using the pumping lemma , let me choose a valid string $W=0011$ $(n=2,m=2$ and $4$ is even$)$.
  2. Let the number of states in the DFA ($C$) be $3$ (I find this step to be fishy)
  3. $|W|\ge C$
  4. Let $W=XYZ$
  5. I choose $X=00,Y=1,Z=1$ such that $|xy| \le C ,|Y| \ge1$
  6. So, for all $i$, $00(1)^{i}1$ should be in $L$
  7. But when $i=2$,String $00111$ is not in $L$, hence this language is not regular.

But I came across a regular expression for the same language:

$$0(00)^*1(11)^*+(00)^*(11)^*$$ Is there a flaw in my pumping lemma or the regular expression? Someone please help me out.

$\endgroup$
  • $\begingroup$ Should i chose the pumping length as 'p' only, and not some constant value? $\endgroup$ – Vinod Pn Jan 31 '17 at 17:11
  • 2
    $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Jan 31 '17 at 18:09
  • 1
    $\begingroup$ This language is indeed regular -- constructing an NFA is a (very easy) exercise. $\endgroup$ – Raphael Jan 31 '17 at 18:11
2
$\begingroup$

You seem to have misunderstood the pumping lemma.

Taking the definition from Introduction to the Theory of Computation by Michael Sipser

If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

  1. for each $i ≥ 0, xy^i z \in A$,

  2. $|y| > 0$, and

  3. $|xy| \le p$.

A few points:

  • The lemma only says that a pumping length $p$ exists. You do not get to choose the value of $p$. So, you cannot say that let $p=3$.
  • For every string $s$ in the language with length at least $p$, it may be divided into three pieces, $s=xyz$. Notice that this again talks only of the existence of a way to split $s$ into $xyz$ given that $A$ is regular. So, you do not get to choose how the string splits into $x$, $y$, and $z$ in the general case. Finding a split that does not satisfy the conditions does not show that the language is not regular. You need to find such a string that cannot be split as stipulated by the definition to show that a language is not regular.
  • Finally, the pumping lemma does not say what happens if $A$ is not regular. So, even a non-regular language may satisfy it, and the pumping lemma cannot be used to show that a language is regular.
$\endgroup$
1
$\begingroup$

You pumping lemma is wrong. The pumping lemma only works on strings that are sufficiently long, yours is not. If we have a string that is sufficiently long(longer then the number of states in the corresponding dfa or nfa) we must have repeated some states, which means that there is a loop somewhere in the path through the dfa to generate this string. We can then infinity repeat this loop and the string is still valid. Your string of length 4 is not sufficiently long to use the pumping lemma on. The language is regular. There are only 2 situations regarding valid strings in this language. If the number of 0's is even, the numbers of 1's is even. And if the number of 0's is odd the number of 1's is odd. Your regular expression covers both of these.

$\endgroup$
  • $\begingroup$ Actually, since there is a 4-state FA for the OP's language, the string $0011$ will work in the PL. However, that's immaterial, since the language is regular and so any PL proof that it isn't will necessarily be wrong. $\endgroup$ – Rick Decker Jan 31 '17 at 19:32

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.