Re: pumping lemma (third try)

From: Mark \(The WannaBe\) (mark_hsn_at_hotmail.com)
Date: 10/15/04 

Date: Fri, 15 Oct 2004 09:45:06 +0200

"Mark (The WannaBe)" <mark_hsn@hotmail.com> wrote in message
news:ckma9a$16r9$1@news.cybercity.dk...
> ----- Original Message -----
> From: "Rick Decker" <rdecker@hamilton.edu>
> Newsgroups: comp.theory
> Sent: Thursday, October 14, 2004 3:56 PM
> Subject: Re: pumping lemma (third try)
>
>
>>
>>
>> Mark (The WannaBe) wrote:
>>> Hi
>>>
>>> I have tried to learn from Rick Decker's, Robin Chapman's and Andrew
>>> Duncan's comments and put my hands on a new wannabe trial using the
>>> pumping lemma on the problem below. My wannabe attempt of a proof is
>>> between the lines --*--*---
>>>
>>> The problem statement is as follows:
>>>
>>> Prove that the following language L is not regular:
>>>
>>> L = {The set of string of 0's and 1's that are not of the form xx^R,
>>> that is, some string x followed by its reverse.}
>>>
>>> (This is the problem 4.1.2.f from the textbook "Introduction to Automata
>>> Theory, Languages, and Computation" by Hopcroft et al)
>>>
>>> --*--*---
>>> I will assume that L is regular and therefore the pumping lemma (PL)
>>> applies. I.e. I can decompose a string w belonging to L into x, y and z
>>> and pump up (repeat) the string, y, k times where 0<=k and get a new
>>> string xy^kz , which is also belonging to L.
>>>
>>> I chose the PL string w to be w = a_(1) a_(2) . a_(n) a_(n) a_(n-1) .
>>> a_(1) and I choose the PL number to be n>0
>>
>> It would be better to say "where n is the integer of the PL" since
>> you're not really chosing the value of n. That's just a minor
>> quibble, but when you're doing a proof you should try to be
>> as precise as possible.
>>
>>> i.e. that the length of |w|>=n. The symbols of the string are
>>> represented by the symbol, a, and a subscript is used to indicate the
>>> positions of the reversed symbols in the reversed string.
>>
>> It might be a bit clearer if you chose something more concrete for w,
>> like w = 0^n 1 1 0^n. Remember, you have the freedom to pick w to
>> be any string, as long as (a) it is in L, (b) its length is at least n,
>> and, for strategic purposes, (c) pumping it up or down will always give
>> you a string not in L.
>>>
>>> Now I will divide the PL string w into the PL substrings x, y and z. We
>>> know that xy = a_(1) a_(2) . a_(i-1) a_(i) where 0<i<=n because |xy|<=n.
>>> Let x = a_(1) a_(2) . a_(i) and y=a_(i+1) .. a_(n) where 0<=i<n.
>>
>> You can't always guarantee that y will have that form. Remember, all
>> you know is that (a) y is nonempty and (b) |xy| <= n, so all you can say
>> is that there are integers r and s with 0 <= r < s <= n such that
>>
>> x = a_1 ... a_r
>> y = a_(r+1) ... a_s
>>
>> if r > 0 or
>>
>> x = the empty string
>> y = a_1 ... a_s
>>
>> if r = 0
>>
>>> I.e. y will always contain at least a_(n) because the pumping lemma
>>> requires that y must not be the empty string. Let us chose k=0. Then xz
>>> = a_(1) a_(2) . a_(i) a_(n) a_(n-1) . a_(1) where 0<=i<n. We know that
>>> at least one symbol, a_(n), will never be reversed for k=0, so xz cannot
>>> be of the form xx^R, i.e. we have a contradiction because we cannot have
>>> L being regular without that PL applies, so L cannot be regular.
>>
>> You can't conclude that. This is why I suggested picking a particular
>> string for w. Suppose, for example, that the a's in your choice of
>> w happened to be all 0 and that y happened to be of even length.
>> Then x(y^i)z would be an even-length string of zeros for any
>> i = 0, 1, 2, ... . Such strings are in L, so you don't get a
>> contradiction and the proof that L isn't regular breaks down.
>>
>> The point here is that you have to pick a w so that no matter what
>> x, y, and z happen to be you'll always get a contradiction.
>>
>> Try it again, using w = 0^n 1 1 0^n and see how it works.
>>
>>
>> Regards,
>>
>> Rick
>>
>> p.s. You'll almost always want to pick a definite string for w,
>> but here is a problem where you don't. Problem 1 is just
>> a warmup; problem 2 is where you can use the PL.
>>
>> 1. Let L2 be the set of all strings over 1, 2 that have no
>> adjacent nonempty equal substrings (so 1212 isn't in L2, since the
>> string 12 is repeated adjacently and 1211 isn't in L either
>> since the string 1 appears as an adjacent repeat at the end).
>> Show that L2 is regular.
>>
>> 2. Let L3 be defined like L2, except that it is the set
>> of all strings over 1, 2, 3 having no adjacent nonempty
>> equal substrings. Show that L3 isn't regular. Hint:
>> L3 is infinite.
>>
>
>
> Hi Rick
>
> Thank you so much for taking your precious time to read through, comment
> and answering my wannabe trials and questions.
>
> I have tried to do my best on the questions you came up with in your last
> posting. I have tried to go through your suggestions for how I could
> improve my understanding of the pumping lemma in the three sections below
> Trial 1, Trial 2 and Trial 3. Trial 1 is my retrial on my last solution,
> which turned out to be a total failure. I have chosen w as you suggested
> and redone the proof. Trial 2 and Trial 3 is my wannabe solutions for your
> problems stated in your ps. I hope that my solutions are showing just a
> little bit that I have learned something from your postings.
>
> Trial 1:
>
> Prove that the following language L is not regular:
>
> L = {The set of string of 0's and 1's that are not of the form xx^R, that
> is, some string x followed by its reverse.}
>
> (This is the problem 4.1.2.f from the textbook "Introduction to Automata
> Theory, Languages, and Computation" by Hopcroft et al)
>
> --*--*---
> I will assume that L is regular and therefore the pumping lemma (PL)
> applies. I.e. I can decompose a string w belonging to L into x, y and z
> and pump up (repeat) the string, y, k times where 0<=k and get a new
> string xy^kz , which is also belonging to L.
>
> I choose the PL string w to be w = 0^n110^n where n is the PL number i.e.
> n>0 and where the length of the PL string w is |w|>=n.
>
> Now I will divide the PL string w into the PL substrings x, y and z. We
> know from PL that |xy|<=n i.e. xy = 0^t where 0<t<=n.
> Let r + s = t and s>0 then x = 0^r = 0^(t-s) and y = 0^s. Now we choose
> the PL k to be k=0 and we have xz=0^(t-s)110^n.
> When k=0 there will always be at least one more 0 in 0^n than in 0^(t-s)
> so 0^(t-s)110^n cannot be a of the form xx^R and therefore 0^(t-s) so
> 0^(t-s)110^n cannot be a member of L and we have a contradiction with the
> assumption. The conclusion must be that L is not a regular language.
> --*--*--
>
> I hope I did better this time? I was surprised that my last attempt was a
> totally failure, it is really hard to be a wannabe. :-) It helped that you
> wrote that I could/should choose a specific PL string w, I was beginning
> to think that should let w be open for all possible constructions, but
> that is just the wannabe me, who misunderstood what the pumping lemma is
> all about.
>
> Trial 2:
>
> Let L2 be the set of all strings over 1, 2 that have no
> adjacent nonempty equal substrings (so 1212 isn't in L2, since the
> string 12 is repeated adjacently and 1211 isn't in L either
> since the string 1 appears as an adjacent repeat at the end).
> Show that L2 is regular.
>
> --*--*--
> The only strings belonging to L2 is {1, 2, 12, 21, 121, 212} and no more
> (maybe the empty string?).
> The minimal elements of L2 are 1 and 2 and they obvious belong to L2. 1
> can only be extended with 2 to get 12 which also belongs to L2 and 2 can
> only be extended with 1 giving 12 which also belongs to L2. 12 can only be
> extended with 1 giving the string 121, which also belongs to L2 and 21,
> can only be extended with 2 giving the string 212 which also belongs to
> L2. No more string can be constructed which belongs to L2. I cannot extend
> 121 with 1 because then the 1's would repeat and I cannot extend 121 with
> 2 because then 12 would repeat. I cannot extend 212 with 1 because then 21
> would repeat and I cannot extend 212 with 2 because then the 2's would
> repeat. Therefore L2 most be finite and all finite languages are regular.
> --*--*--
>
> I did my best on this one. I don't know if I can proceed with a proof like
> this. I have bought Michael Sipser's book "Introduction to the Theory of
> Computation" as a supplement to the textbook "Introduction to Automata
> Theory, Languages, and Computation" by Hopcroft et al. He mention
> something he calls proof by construction, but I am to much of a wannabe to
> figure out if that is what I just did in trial 2. If the empty string were
> a part of L2 then I would have started by constructing 1 and 2 from the
> empty string.
>
>
> Trial 3:
>
> 2. Let L3 be defined like L2, except that it is the set
> of all strings over 1, 2, 3 having no adjacent nonempty
> equal substrings. Show that L3 isn't regular. Hint:
> L3 is infinite.
>
> --*--*--
> We will assume that L3 is regular and therefore the pumping lemma (PL)
> applies.
> We will choose the PL string w to be any sequence of 1, 2 and 3 where
> there are no adjacent equal substrings.
> Let n be the PL number. Now decompose w into x, y and z such that |xy|<=n
> and |y|>0. Now choose the PL k to be k=2 and construct the string xyyz.
> Now you have a string, xyyz, where no matter what y is then you have two
> adjacent nonempty equal substrings, i.e. that xyyz does not belongs to L3
> and our assumption was wrong, L3 cannot be regular because PL did not
> apply.
> --*--*--
>
> Was that the way to do it? I have the feeling that I should have proved
> that L3 is infinite but I am too much of a wannabe to know how to do that.
>
> Kind regards
> Mark (The WannaBe)

Hi

Based on Jim Nastos' postings I have tried to refine my prove of Rick Decker's
problem of L3 being not regular. Jim told me about ternary square-free
words. I have not constructed/defined a specific ternary square-free word
because I believe that it was a part of Rick Decker's statement of the L3
problem. But it could be the wannabe part of me totally misunderstanding
what the problem is trying to teach me. But I try to use the fact that PL
assumes that for a regular language to be infinite then there must exist
substrings, which can be repeated indefinitely. And L3 is defined so that
this cannot be the case, i.e. that there must not exist any repeated
substrings in strings belonging to L3. Again my attempt of a prove is
contained between the lines --*--*--.

Trial 3:

Let L2 be the set of all strings over 1, 2 that have no
adjacent nonempty equal substrings (so 1212 isn't in L2, since the
string 12 is repeated adjacently and 1211 isn't in L either
since the string 1 appears as an adjacent repeat at the end).

2. Let L3 be defined like L2, except that it is the set
of all strings over 1, 2, 3 having no adjacent nonempty
equal substrings. Show that L3 isn't regular. Hint:
L3 is infinite.

--*--*--
We will assume that L3 is regular and therefore the pumping lemma (PL)
applies. Let n be the PL number. We will choose the PL string w to be any
ternary square-free word, i.e. a sequence of 1, 2 and 3 where there are no
adjacent equal substrings and with a length |w|>=n (i.e. we assume that L3
is infinite because we can choose any n we like, if L3 was finite then we
could not apply PL and L3 would be regular). We know that L3 is in fact
infinite because the existence of arbitrary long ternary square-free words
is a well-known fact (*). Now decompose w into the PL substrings x, y and z
such that |xy|<=n and |y|>0. Now choose the PL k to be k=2 and construct the
string xyyz. Now you have a string, xyyz, where no matter what y is chosen
to be then you have two adjacent nonempty equal substrings, i.e. that xyyz
does not belongs to L3 and our assumption was wrong, L3 cannot be regular
because PL did not apply.
--*--*--

(*) Actually I don't know but I take my chance on this because from Jim
Nastos' posting and from for example mathworld
(http://mathworld.wolfram.com/SquarefreeWord.html) it seems to be so. But I
do not know if I refer to ternary square-free words in a proof like this, if
I am not able to prove their existence my self?

I have tried to be as precise as a wannabe like me can be. Is this
refinement of the L3 any better than the previous trial, or did I fail just
as badly as last time?

Kind regards
Mark (The WannaBe)

Relevant Pages

  • Re: pumping lemma (third try)
    ... some string x followed by its reverse.} ... > I will assume that L is regular and therefore the pumping lemma ... > Now I will divide the PL string w into the PL substrings x, ...
    (comp.theory)
  • Re: pumping lemma (third try)
    ... >> Duncan's comments and put my hands on a new wannabe trial using the ... >> pumping lemma on the problem below. ... I can decompose a string w belonging to L into x, ... >> being regular without that PL applies, ...
    (comp.theory)
  • Re: regex help
    ... On Sep 17, 8:58 am, Jesse Houwing ... i'm trying to see if a string ends with teh below ... Your regular expression is correct. ...
    (microsoft.public.dotnet.framework.compactframework)
  • Re: need help on regex
    ... i'm trying to see if a string ends with teh below ... can someone help me out with teh correct pattern ... You can solve this issue with regular expresions with the following expression: ...
    (microsoft.public.dotnet.framework.windowsforms)
  • Re: pumping lemma (third try)
    ... Mark (The WannaBe) wrote: ... > comments and put my hands on a new wannabe trial using the pumping lemma on ... some string x followed by its reverse.} ... > I will assume that L is regular and therefore the pumping lemma ...
    (comp.theory)
Loading