[lojban] Re: Official parser and "lo ni'a zu crino"

[Rob Speer <lojban-out@lojban.org>]

On Fri, Apr 09, 2004 at 01:15:38PM -0700, Robin Lee Powell wrote:
> That's impossible.  For one thing, I'm fairly certain that proving
> equivalence of two CFGs is equivalent to the halting problem.  For
> another, the current 'grammar' isn't formalized at all in many major
> respects (the pre-processing and elidable terminators), so there's
> nothing to write a proof against.

It is equivalent to the halting problem: that is, doable in the vast
majority of cases. Just not all.

Here's two equivalent CFGs:

Start -> e

Start -> foo
foo -> e

Nevertheless, it is a bit overdemanding for Bob to require you to prove
complete equivalence.
-- 
Rob Speer