f



Pumping Lema (question about constant choice)

Dear Sirs,

I am facing the follown ex. and i'd very appreciate
if anyone could give some hints.

Let be  L=3D{a^ib^jc^k | i !=3Dj or j !=3Dk}. Suppose that to prove
L is not regular using the PL it was chosen the following z:

       z=3Da^kb^{k!+k}c^{k!+k}

where k is the constant of PL. The question is, why this choice (
and not some else?)


Thanks in advance!

Cordialmente,

     Leonardo

 "N=E3o existe um caminho para a paz; a paz =E9 o caminho"
                                    Mahatma Gandhi


0
leob4 (27)
11/19/2003 1:02:03 AM
comp.theory 5139 articles. 1 followers. marty.musatov (1143) is leader. Post Follow

2 Replies
338 Views

Similar Articles

[PageSpeed] 0


Leonardo Barbosa e Oliveira wrote:

> Dear Sirs,
> 
> I am facing the follown ex. and i'd very appreciate
> if anyone could give some hints.
> 
> Let be  L={a^ib^jc^k | i !=j or j !=k}. Suppose that to prove
> L is not regular using the PL it was chosen the following z:
> 
>        z=a^kb^{k!+k}c^{k!+k}
> 
> where k is the constant of PL. The question is, why this choice (
> and not some else?)
> 
Good question. A general answer would be that one gets

better at picking test strings with practice. Let's see
what the solver might be thinking while doing this problem.

<begin mind-reading transcript>

Okay, I need a sufficiently long word in L so that when I
pump it, I'll get a string not in L. I'll let the last two
exponents be the same and let the first be different from them,
so my test word will look like z = a^{i}b^{j}c^{j}.

Now, since I've worked a bunch of problems like this before,
I'll let n be the integer of the PL and try x = a^{n}b^{j}c^{j}.
I'll fill in a value for j once I figure out what I need.

The PL says that I can write z = uvw, where |uv| <= n and
|v| > 0, so by my choice, uv, and hence v, will be a^{t},
with 1 <= t <= n.  That means that the pumped string
uv^{i}w will be a^{n - t + it}b^{j}c^{j}, so j = j(n) will
have to be a function of n for which

n - t + it = j(n)

or, grouping terms,

n + t(i - 1) = j(n).

That n on the left is a bother, so I'll try j(n) = n + (something)
which will lead me to

t(i - 1) = something

Now all I know about t is that it is a positive integer <= n.
How can I pick (something) so that it will equal t(i - 1), where
I have free choice of i, but don't know the value of t?  Well,
certainly t will have to divide both sides of the equation...
Aha! if (something) is n!, t will divide it for any 1 <= t <= n.

I'm done!  If I let (something) be n!, then no matter what
value t is, it will divide n! so we'll have

i - 1 = n! / t

and since I can pick i to be any nonnegative integer, I
can pick it to be (n! / t) + 1. Doing so will make all
three exponents equal, so I'll have a pumped string not in L,
which will give me the contradiction I need, using the
test string x = a^{n}b^{n! + n}c^{n! + n}.

<end mind-reading>

There are some morals to this story. First, PL proofs require
a lot of practice before one is fluent in them. Just about
the only way to get good is to do *lots* of examples. Second,
relax and realize that once you're finished with this section,
you'll rarely encounter PL proofs of nonregularity. Finally,
as has been pointed out in this NG recently, there are
points of view one acquires after a while that are better
for establishing nonregularity than "blind" adherence to the PL
(much as one sees in calculus, where one comes to realize
that you don't always need L'Hopital's rule to evaluate
limits of the 0/0 variety).


Hope this helps, even if only a little.

Rick


p.s. For this problem, you could also argue that L' \intersect a*b*c*
is just the a^{n}b^{n}c^{n} language, and I'll bet you know that
that language isn't regular. Then, by the fact that a*b*c* is
regular and that regular languages are closed under complement
and intersection, L couldn't possibly be regular.  Much more elegant,
IMO.

R.

0
rdecker (166)
11/19/2003 3:07:49 AM
many thanks! I gonna look at it.
Sure it will help.


regards

     Leonardo

 "N=E3o existe um caminho para a paz; a paz =E9 o caminho"
                                    Mahatma Gandhi


On Tue, 18 Nov 2003, Rick Decker wrote:

>
>
> Leonardo Barbosa e Oliveira wrote:
>
> > Dear Sirs,
> >
> > I am facing the follown ex. and i'd very appreciate
> > if anyone could give some hints.
> >
> > Let be  L=3D{a^ib^jc^k | i !=3Dj or j !=3Dk}. Suppose that to prove
> > L is not regular using the PL it was chosen the following z:
> >
> >        z=3Da^kb^{k!+k}c^{k!+k}
> >
> > where k is the constant of PL. The question is, why this choice (
> > and not some else?)
> >
> Good question. A general answer would be that one gets
>
> better at picking test strings with practice. Let's see
> what the solver might be thinking while doing this problem.
>
> <begin mind-reading transcript>
>
> Okay, I need a sufficiently long word in L so that when I
> pump it, I'll get a string not in L. I'll let the last two
> exponents be the same and let the first be different from them,
> so my test word will look like z =3D a^{i}b^{j}c^{j}.
>
> Now, since I've worked a bunch of problems like this before,
> I'll let n be the integer of the PL and try x =3D a^{n}b^{j}c^{j}.
> I'll fill in a value for j once I figure out what I need.
>
> The PL says that I can write z =3D uvw, where |uv| <=3D n and
> |v| > 0, so by my choice, uv, and hence v, will be a^{t},
> with 1 <=3D t <=3D n.  That means that the pumped string
> uv^{i}w will be a^{n - t + it}b^{j}c^{j}, so j =3D j(n) will
> have to be a function of n for which
>
> n - t + it =3D j(n)
>
> or, grouping terms,
>
> n + t(i - 1) =3D j(n).
>
> That n on the left is a bother, so I'll try j(n) =3D n + (something)
> which will lead me to
>
> t(i - 1) =3D something
>
> Now all I know about t is that it is a positive integer <=3D n.
> How can I pick (something) so that it will equal t(i - 1), where
> I have free choice of i, but don't know the value of t?  Well,
> certainly t will have to divide both sides of the equation...
> Aha! if (something) is n!, t will divide it for any 1 <=3D t <=3D n.
>
> I'm done!  If I let (something) be n!, then no matter what
> value t is, it will divide n! so we'll have
>
> i - 1 =3D n! / t
>
> and since I can pick i to be any nonnegative integer, I
> can pick it to be (n! / t) + 1. Doing so will make all
> three exponents equal, so I'll have a pumped string not in L,
> which will give me the contradiction I need, using the
> test string x =3D a^{n}b^{n! + n}c^{n! + n}.
>
> <end mind-reading>
>
> There are some morals to this story. First, PL proofs require
> a lot of practice before one is fluent in them. Just about
> the only way to get good is to do *lots* of examples. Second,
> relax and realize that once you're finished with this section,
> you'll rarely encounter PL proofs of nonregularity. Finally,
> as has been pointed out in this NG recently, there are
> points of view one acquires after a while that are better
> for establishing nonregularity than "blind" adherence to the PL
> (much as one sees in calculus, where one comes to realize
> that you don't always need L'Hopital's rule to evaluate
> limits of the 0/0 variety).
>
>
> Hope this helps, even if only a little.
>
> Rick
>
>
> p.s. For this problem, you could also argue that L' \intersect a*b*c*
> is just the a^{n}b^{n}c^{n} language, and I'll bet you know that
> that language isn't regular. Then, by the fact that a*b*c* is
> regular and that regular languages are closed under complement
> and intersection, L couldn't possibly be regular.  Much more elegant,
> IMO.
>
> R.
>
>

0
leob4 (27)
11/19/2003 10:54:36 AM
Reply: