Существует ли алгоритм перехода от контекстно-зависимой грамматики к линейным ограниченным автоматам?

Question

Я изучаю LBA (линейные ограниченные автоматы). Пытаюсь понять, как решить какое-то упражнение.

Поэтому мне интересно, есть ли простой способ создать LBA с учетом контекстно-зависимой грамматики.

Это похоже на то, как вы можете перейти от грамматики LR к DFA (детерминированным конечным автоматам).

заранее спасибо

Answer 1

Поскольку контекстно-зависимые грамматики не имеют каких-либо ограничительных правил производства, вы можете просто использовать исчерпывающий поиск.

Начиная со строки, вы можете недетерминированным образом выбрать производство, которое нужно отменить. Это не может увеличить длину ввода. Повторяйте до тех пор, пока вы не достигнете пустой строки (в этом случае вы принимаете) или не сможете отменить любое производство (в этом случае вы отклоняете).

Это эскиз, но заполнить детали просто.