Contextsensitive grammars define exactly the langauges acceptable by nondeterministic LBA. But how about deterministic LBA - is there a grammar type capturing exactly the languages acceptable by this restricted automaton type? (Just as contextfree grammars capture nondeterministic, and LR-k grammars capture deterministic PDAs.)

Of course, as the first LBA problem is still open (http://en.wikipedia.org/wiki/Linear_bounded_automaton#LBA_problems), it would have to be an open question if this grammar type in question is equivalent to contextsensitive grammars. However, if existing, it would provide an alternate approach to solve the first LBA problem.

I don't think there is such a grammar type (I would have heard about it...), but if not, maybe someone can elaborate, why it is so difficult to come up with it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.