🚀 go-pugleaf

To see why "copy languages" are non-regular, learn a pumping lemma for CFLs, 
as was just suggested.

I recently read an interesting explanation of why copy languages are non regular.
Think about "dependencies" in a string, which are produced by the process of 
derivation.  Rather than be formal, I'll give an example.  For palendromes, the
dependencies are nested.  For example:

            a  b   b  a   a   a   b   b   a
            |  |   |  |       |   |   |   |
            |  |   |  +-------+   |   |   |
            |  |   +--------------+   |   |
            |  +----------------------+   |
            +-----------------------------+
                      
This property holds for all context free languages.  However, consider the 
dependencies for non CF languages.  For example, one from a copy language:

            a   b   b   a   a   b   b   a
            |   |   |   |   |   |   |   |
            |   |   |   +-------^---^---+
            |   |   +-----------^---+    
            |   +---------------+  
            +---------------+
The dependencies cross.  This is evidence that a more complicated process
took place when they were generated, one where the productions had to "be aware"
of other productions "in context".

I thought this was cute.  Incidentally, I read about it in "The Linguistics of DNA",
Davide B. Searls, American Scientist, Vol 80, Nov-Dec 1992, pp 579--591.
-- 
James A. Foster                           foster@cs.uidaho.edu
Universty of Idaho                        Dept. of Computer Science