CFG是否使用可判斷的nil語言？

如果我有一個上下文無關文法G，使得G的語言爲零，那麼G是可確定的嗎？CFG是否使用可判斷的nil語言？

我知道答案是肯定的，但我無法證明這一點。我的第一個想法是說，只有一個狀態q1，它是圖靈機的啓動狀態和接受狀態，相當於G.此機器將不接受輸入並立即停止並接受，因爲它已達到接受州。這是一個可以接受的答案，還是我在這裏？

編輯：

喬爾下面說的，我描述的語言接受所有字符串。爲了解決這個問題，我提出了第二臺機器G'。 G'具有3個狀態，起始狀態q1，接受狀態q2和拒絕狀態q3。 q1在G'的字母表中的所有符號上過渡到q3，q2也是如此。 q1有一個ε過渡到q2。因此，如果在饋送給G'的字符串中存在任何符號，則G'將被拒絕。如果沒有符號，唯一的選擇是將epsilon轉換到accept狀態。聽上去怎麼樣？

編輯：

將上述溶液被證明接受語言L（G'）= { 「」}。

來源

2011-03-22 Darkhydro

我想我們可能會使用不同的術語。「G的語言是零」是指L（G）= {}，即空集？或者，你的意思是L（G）= {「」}，即由恰好一個字符串組成的語言，即空字符串？人們通常認爲，不存在接受狀態的轉變，所以當你達到接受狀態時，你會停下來。有了這個假設，你的原始TM接受了一切。您在Edit中描述的TM接受L = {「」}，我認爲這是您的意圖。我在答覆中描述的TM沒有任何結果。也就是說，它接受L = {}。 – 2011-03-22 07:08:07

@Joel我的意思是L（G）= {nil}，我相信這相當於你的陳述L（G）= {}。如果從未達到接受狀態（因爲沒有？），可以多解釋一下答案如何接受該語言（因爲沒有？） – Darkhydro 2011-03-22 17:18:12

根據定義，如果機器_M_在給定輸入_s_時達到接受狀態，則接受字符串_s_。同樣根據定義，_L（M）_，被稱爲「M接受的語言」，是_M_接受的所有字符串的集合。 _L（M）_是一組**字符串。但實際上，這一套可能是空的。如果機器沒有接受狀態，那麼它不可能接受任何給予它的字符串。因此_L（M）_是空集。您的G'機器只接受一個字符串，即零長度字符串。因此，_L（G'）_ = {「」}。 – 2011-03-22 22:53:04

正如你所說，答案是肯定的。一般的證明是，給定一個CFG G你可以很容易（很好地）構造一個TM來模擬使用該語法的派生。但是，您正在尋找空白語言的簡短證明。（事實上，在這種情況下你有一個CFG是無關緊要的。）

你是正確的軌道，如果你可以構造一個總是暫停給定語言L的TM，那麼L是可判定的。但是，您描述的機器實際上會接受每個字符串，即由字母表上的每個可能字符串組成的語言。這是因爲如果啓動狀態也是一個接受狀態，那麼圖靈機將在啓動時立即接受。它不必讀取整個輸入字符串（或其任何部分）以接受。

要定義不接受任何內容的TM，讓接受狀態集爲空。爲確保您的機器始終處於停止狀態，您的轉換功能也可以爲空。

來源

2011-03-22 06:05:59

我不確定我是否理解。我的印象是，機器不僅要停下來，還要接受。機器可以暫停然後拒絕語言，因爲（我認爲）在您的示例中就是這種情況。 – Darkhydro 2011-03-22 06:25:01

關於術語/概念的注意事項。我們討論接受或拒絕給定字符串的機器。由此我們定義了「M接受的語言」的概念，並且我們說「機器M接受語言L」。但是，我們並不是說「機器M拒絕語言L」。相反，你會說「M接受的語言不等於L」。 – 2011-03-22 23:41:30

CFG是否使用可判斷的nil語言？

回答

相關問題