是否有一種從上下文敏感語法轉換爲線性有界自動機的算法？

Question

我正在學習LBA（線性有界自動機）。試圖找出如何解決一些exersise。

所以我想知道是否有一個簡單的方法來使LBA給出一個語境敏感的語法。

這就像你如何從LR語法到DFA（確定性有限自動機）一樣。

在此先感謝

Answer 1

由於上下文有關文法沒有任何收縮產生式規則，你可以使用窮舉搜索。

從字符串開始，您可以非確定性地選擇要撤消的作品。這不能增加輸入的長度。重複，直到你到達空字符串（在這種情況下你接受）或無法撤銷任何生產（在這種情況下，你拒絕）。

這是一個草圖，但填寫細節很簡單。