That crossword thing.

[ja...@ioctl.org]

Sam, need to apologise - I made the spurious claim that (...?)\1* didn't
define a regular language. I was, obviously, imagining the situation where
the alphabet was infinite (as you do). Over a finite alphabet the above
_is_ regular, but for the slightly awkward reason that it's equivalent to

(aaa)+|(aab)+|(aac)+| ... |(zzy)+|(zzz)+

... which is not an observation that is particularly useful, I'll admit.

As to the related question of whether

(AB)\1

(with A and B nontrivial CF expressions) is context-free: it isn't;
consider

(a+b+)\1

which isn't context-free (I'm not sure it's even context-sensitive - it
falls under the "can count two things, not three" rule).

--
jan grant http://ioctl.org/jan/
Whenever I see a dog salivate I get an insatiable urge to ring a bell.

[Sam Phippen]

I agree with your analysis completely :)

Thanks
--
Sam Phippen

> --
> You received this message because you are subscribed to the Google Groups "BrisFunctional" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to brisfunctiona...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[ja...@ioctl.org]

On Thu, 28 Feb 2013, Sam Phippen wrote:

> I agree with your analysis completely :)

... that "insight", however, turns out to be useful - it brings the solver
time down from about 90-odd seconds to five! (the resulting RE is about
58k long in text form and has nigh on 50,000 states :-) )

--
jan grant http://ioctl.org/jan/

Syntactic sugar causes cancer of the semi-colons.

[Sam Phippen]

Nice: that space/time tradeoff.

Thanks
--
Sam Phippen