帶有非確定性圖靈機的上下文敏感語言

我知道線性邊界自動機（LBA）接受的語言是一種上下文敏感語言。而LBA是一個非確定性的圖靈機。

任何想法如何將所有這些聯繫起來，並顯示語言是上下文敏感的？

2011-11-30 user1004413

正如您可能已經想到的那樣，CSTheory.stackexchange需要研究級別的問題。但是，math.stackexchange非常適合這樣的問題。另外，他們支持LaTeX的正確格式化答案:) –

由於templatetypedef的回答有一些缺陷（我將在註釋中第二指出），我給一個快速的回答你的問題：

語言是上下文敏感的，如果（且僅當），你可以使用定義爲L的線性空間給出非確定性圖靈機。對於任意整數n，設L = {a^nb^na^n};對於任意整數n，設L = {a^nb^na^n}這裏的^ n表示符號a的n個並置。這是一種典型的上下文敏感語言。你可以給出一個LBA來表明L對上下文敏感：

圖靈機M'猜測'（感謝不確定性）n [換言之，你可以說'非確定性搜索的每一個分支樹嘗試另一個n]，然後檢查輸入是否匹配^ nb^na^n。您需要記錄n個單元來存儲n，匹配可能需要（如果實現平凡）另一個記錄n個單元。作爲n + 2log n，這臺機器只需要線性空間，因此是一個LBA，因此L是上下文敏感的。

來源

2011-11-30 15:45:34

是否有證明NSPACE（n）= CSL？我從來沒有聽說過這個結果，但它看起來非常酷！ – templatetypedef

是的，它已於1969年得到證實;我無法找到保存證明的公開文件，ComplexityZoo（由斯科特·阿倫森複雜類問題，一個很不錯的參考）持有http://www.sciencedirect.com/science/article/pii/S0022000069800322作爲參考。也許谷歌吐出了一些公開可用的證據。 –

這不是一個確切的答案，但是由於上下文相關語言正是那些由線性有界的自動機（與O（N A TM）在其磁帶空間）接受，上下文敏感的語言正是那些在DSPACE（n）中。而且，我們知道NTIME(n) = DSPACE(n)。這意味着如果你可以找到一個線性時間的NTM來決定一些語言L的成員身份，那麼這個語言必須是上下文敏感的。然而，仍然可能存在一種沒有線性時間NTM的上下文敏感語言（我不知道是否有明確的答案或者這是否是一個開放的問題），所以這不是一個確切的描述。

希望這會有所幫助！

來源

2011-11-30 03:43:32 templatetypedef

如上所述，這個答案有一些錯誤：一方面我們不知道DSPACE（n）是否是NTIME（n）的一個子集。相反，這是顯而易見的。另一方面，CSL恰好是NSPACE（n）中的語言，而不是DSPACE（n）中的語言。這是一個開放的問題，但相信DSPACE（n）是NSPACE（n）的一個真正的子集。 –

帶有非確定性圖靈機的上下文敏感語言

回答

相關問題