Re: String Transformation Problem

From: Torben Ęgidius Mogensen (torbenm_at_diku.dk)
Date: 02/03/05 

Date: 03 Feb 2005 10:49:18 +0100

"Thomas A. Li" <tli@corporola.com> writes:

> "Colin Percival" <cperciva@sfu.ca> wrote in message
> news:ctraav$cm9$1@morgoth.sfu.ca...
> > yaoziyuan@gmail.com wrote:
> > > Given two strings S1 and S2, and a set of transformation rules in the
> > > form of:
> > > If string S contains substring SUB1, then SUB1 can be replaced with
> > > SUB2.
> > > Is there a good algorithm that:
> > > (4) determines if S1 can be successfully transformed to S2, without
> > > giving an actual pathway.
> >
> > Unless I'm misremembering something, this is at least as hard as
> > determining if if a Turing machine halts.
>
> Absolutely, the equivalent is Noam Chomsky's context-sensitive grammar.

Actually, Chomsky's unrestricted grammars. Context-sensitive grammars
have the further restriction that the replacement string can not be
longer than the source.

        Torben