0
$\begingroup$

We learn about the Pumping Lemma at the class and I tried to make few examples to understand it...

There I make this example:
Let's say: $L=\{w\in L|w=(0+1)^*1\}$ - i.e. - L is the language of all the words that finish with $1$. (The language is regular of course).

Now, I can take the word: $w=0^{n-1} 1$. $w\in L$ and $|w|\ge n$.
I can take: $u=0^{n-1},v=1,z=\varepsilon$.
$|uv|\le n$ and $|v|>0$, but:
$uv^0z\notin L$ because $uv^0z$ ends with $0$...

What I miss here?
I'd like to understand more where is my mistake...

$\endgroup$
1
4
$\begingroup$

The pumping lemma says that, for every regular language there exists some pumping length $p$* such that blah blah blah.

You made two mistakes. First, you tried to choose $p$ based on a specific word, rather than based on the language as a whole. Second, you chose the wrong value of $p$. In particular, for the language you've given, $p=1$ has the property required of the pumping lemma: for every word $w$ in that language, you can write $w=\epsilon y z$ with $|y|=1$, and you'll find that $\epsilon y^n z$ is in the language for all $n\geq 0$.

$\endgroup$
5
  • $\begingroup$ So, if I'm understand right I need to do it for generally $a,b$ that makes $a+b\le n$ and $b>0$, and not for a specific, I'm right? $\endgroup$ – stud1 Dec 5 '15 at 15:59
  • $\begingroup$ I mean - when I'm choosing $u,v$ and $|u|=a,|v|=b$. Right? $\endgroup$ – stud1 Dec 5 '15 at 16:04
  • 1
    $\begingroup$ Yes and no. Read the statement of the lemma! It's complicated (which is why students have difficulty with it) but some things are existentially quantified (i.e., it might only work for one value and you have to figure out which one) and some are universally quantified (it must work for all values). There exists $n$ such that for all strings $w$ longer than $n$, there exists a split $w=xyz$ [with some properties] such that for all $k\geq 0$, $xy^kz$ is in the langauge. $\endgroup$ – David Richerby Dec 5 '15 at 16:14
  • $\begingroup$ But what I don't understand is two things: 1. can I choose the word $w$? 2. Can I choose how to split it? Or I need to do it generally? (the splitiing) - Thank you! $\endgroup$ – stud1 Dec 5 '15 at 16:59
  • 1
    $\begingroup$ @stud1 We have a reference answer about how to use the pumping lemma. The Computer Science Chat room is probably the best place to ask follow-up questions, since comments aren't a good place to try to have a conversation. $\endgroup$ – David Richerby Dec 5 '15 at 17:30
3
$\begingroup$

The pumping lemma states that "... there exist such $u$, $v$, $z$ that $w = xvz$ ..." but it doesn't state you can divide $w$ into arbitrary three pieces (even provided the other conditions hold).

$\endgroup$
2
  • 1
    $\begingroup$ Isn't that what I just said? $\endgroup$ – David Richerby Dec 5 '15 at 15:43
  • 1
    $\begingroup$ @DavidRicherby Obviously it's not, if you compare them character by character :). Wouldn't it be great If someone could benefit from different ways of expressing ideas? $\endgroup$ – Anton Trunov Dec 5 '15 at 16:04
-1
$\begingroup$

En tu caso esta algo mal planteado Para verificar con el lema de bombeo se sigue los siguientes pasos: k es un conjunto de estados de A Primero tiene q cumplir L=t(A)y w € A

A es un AFD con |k|=n y |w| >= n

a) w=uvz

b)|uv|=n

c)v ≠¶ (¶ es el vacío)

d) u(v^i)z i>=0 u(v^i )z € T(A)

con eso el AFD es A={{q0,q1,q2},{0,1},d,q1,q3} Con cadena w=0100111 u(v^i )z i >=0 y |uv|<=n u=0 v=1 z=00111 n=3 al incrementar i aun w € T(A)

espero entiendas :)

$\endgroup$
1
  • 1
    $\begingroup$ Try English? It would help a bit... $\endgroup$ – Evil Dec 11 '15 at 16:28

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.