theory - Is there an algorithm to go from a Context-sensitive grammar to a linear bounded automata?

Question

I am studying LBA (linear bounded automata). Trying to figure it out how to solve some exersise.

So I wonder if there is an easy way to make a LBA given a Context-sensitive grammar.

This is thinking like how you can go from LR grammar to DFA (deterministic finite automata).

thanks in advance

Answer 1

由于上下文相关语法没有任何收缩生产规则，您可以使用穷举搜索。

从字符串开始，您可以不确定地选择要撤消的产品。这不能增加输入的长度。重复直到您到达空字符串（在这种情况下您接受）或无法撤消任何生产（在这种情况下您拒绝）。

这是一个草图，但填写细节很简单。