On Thu, Oct 25, 2001 at 10:21:07AM -0500, Greg Bacon wrote: > According to that page, the "decision problem that asks wether a certain > string s belongs to the language of a certain context-sensitive grammar > G, is undecidable."
That page is wrong. It is decidable (eventually). (See for example section 3.5.2 of _Parsing techniques - a practical guide_, which can be downloaded from http://www.cs.vu.nl/~dick/PTAPG.html I think there's something in Hopcroft & Ullman too, but I don't have it handy.) Hmm, it's a Wiki page. I'll correct it :-) > Greg, who thinks formal languages and complexity theory are fun .robin. (who agrees with Greg) -- "It really depends on the architraves." --Harl
