🚀 go-pugleaf

In article <1993Jan22.214830.26496@math.ucla.edu> aps@sonia.math.ucla.edu (Alexei Stolboushkin) writes:
>In article <1993Jan21.153028.7679@cs.yale.edu> fischer-michael@cs.yale.edu (Michael Fischer) writes:
>
>...
>
>>limitations of these devices.  To see why {ww | w E {0,1}*} is not
>>regular, for example, you need to know about the pumping lemma for
>>regular sets and other techniques for proving non-regularity.  To see
>>why it is not accepted by a pushdown store machine, it is useful to
>     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>certainly it IS context-free, and therefore accepted by a PDA.

ooops, I thought it is ww' (' for reversion), sorry. Yes, you're right,
for any CF language there is n such that every word in the language
of length >n can be represented as xyzuv, with |yzu|<n, |yu|>0,
and all words xy^k zu^k v are also in the language. So it seems
enough to consider one word of the form:
	0^m 1^m 0^m 1^m, for some m>n,
and all four situations, when yzu consists of 1's only, of 0's only,
of 1's, and 0's, and of 0's and 1's.

A much more interesting exercise (and an instructive one), is to
give an example of a non-CF language satisfying the above pumping
lemma.