Re: pumping lemma (third try)

From: Rick Decker (rdecker_at_hamilton.edu)
Date: 10/15/04 

Date: Fri, 15 Oct 2004 11:38:47 -0400

Mark (The WannaBe) wrote:

<snip. Mark, you should trim your replies to what's relevant.
This saves the reader from having to scroll past a lot of
lines that don't contribute to your reply.>

>
> 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?

Certainly. Unless the reader is *really* picky (or is a teacher with
some reason to disallow citations), there's no problem with citing
a known result. Of course, if this was a course I was teaching, I
wouldn't let a student get away with something like

     [My homework problem] Show that if L1 and L2 are regular
     languages, then their symmetric difference is also regular.

     [Student answer] This is true by Theorem 2.12 in Chen and
     Pognowski's _Regular Languages for Dummies_.

In this case, the point of the exercise was to give the student
some practice, so a mere citation would defeat my purpose. If
you ever get to doing research and publishing your work you
can get away with saying things like "It is a simple consequence
of Gbrtczx's Lemma that ..." knowing that the reader will have
to think for several hours about why.
>
> 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?

You don't have to beat yourself up like that. Your previous result
was good and this refinement is better.

Regards,

Rick

p.s. Wait until you get to context-free languages. There's a pumping
lemma for those and it's a lot uglier to use than the one for regular
languages. <evil grin, demonic chortle>

Relevant Pages

  • Re: Invariant with DIGIT-CHAR-P and the reader.
    ... How else would the producer of such a string mean it to be ... CL reader parses as numbers things that "look like a number". ... > treated in ways that a naive Lisp program might be trying to mimic ... if your data contains Unicode characters, ...
    (comp.lang.lisp)
  • Re: SqlDataReader Function From a VB6 refugee
    ... Also the Reader is for connected operations i.e. the underlying connection ... Shared Function Create_SQL_DataReader(ByVal sDate As String) As ... Dim SQLConn As New SqlConnection ...
    (microsoft.public.dotnet.framework.adonet)
  • Re: inputstream -> string
    ... den aus dem Reader gelesenen char-Buffer ... StringWriter sw = new StringWriter; ... Kein Encoding anzugeben, ... private String readStream ...
    (de.comp.lang.java)
  • Re: Array of UDT
    ... reader and not reader ... Excel, PowerPoint, and VBA add-ins, tutorials ... r_sname As String ... Dim rngCommRng As Range ...
    (microsoft.public.excel.programming)
  • LÖSUNG: Problem Zugriff auf Access
    ... Der Ansatz von Mark hat mir weitergeholfen. ... Conn fuer die Seite als Objekt bestehen lassen, ... Dim Conn As New System.Data.OleDb.OleDbConnection(_ ... Dim Reader As System.Data.OleDb.OleDbDataReader ...
    (microsoft.public.de.german.entwickler.dotnet.asp)