computation-theory

3熱度

2回答

語言是可判定的如果TM識別語言並進入接受或拒絕狀態。作爲開發者。我認爲這很重要，因爲這意味着我們可以確定程序是否包含緩衝區溢出或死鎖。此外，下列問題是不可判定的：程序是否曾經訪問未初始化的變量。兩個上下文無關文法是否描述相同的語言。是否有所作爲，如果參數子程序通過引用或複製的結果通過在你會說什麼都是可判定的關鍵點，爲什麼是可判定的重要判定性方面（尤其是一個開發者）。注意：子彈點在答案上很

-3熱度

2回答

構造以下語言的DFA：L = {a^n b^n | n> = 1}

在語言中，n是權力，但我不知道如何寫。

1熱度

2回答

上下文無關語言中的抽吸引理

A = {0^a 1^b 2^c | a < b < c} 我需要證明A不是上下文無關的。我猜我必須使用Pumping引理來解決這個問題，但是如何？

4熱度

3回答

爲什麼這是一個無效的圖靈機？

在進行考試修改時，我無法回答Sipser所着的「計算理論導論」一書中的以下問題。不幸的是，這本書中沒有解決這個問題的方法。解釋爲什麼以下不是合法的圖靈機。 M = { 的輸入是在變量x1一個多項式p，...，XN 嘗試X1的所有可能的設置，...，x N爲整數值在所有這些設置上評估p 如果這些設置中的任何一個評估爲0，則接受;否則拒絕。 } 這讓我瘋狂！我懷疑這是因爲這組整數是無限的？這是否超

1熱度

1回答

爲數值常數

正則表達式Sipser的書計算的理論，以下給出：數值常數，其可包括分數部分和/或符號可被描述爲在語言中的一員（+ U-U e）（D + U D + .D * UD * .D +）其中D = {0,1,2,3,4,5,6,7,8,9}是十進制數字的字母表。生成的字符串的示例是：72，3.14159，+7。和-.01。在這裏我不明白接受D +或D *聯合的目的是什麼？此外爲什麼添加第三點

4熱度

1回答

如何獲得DFA交集？

我們如何將兩個dfa結合使用相交法？

0熱度

2回答

證明融通α的問題是NP

試圖刷上計算的理論，但我不知道的解決這個： Prove that the problem of factoring α is in NP. 我有一種感覺，可能涉及到找到一個NP問題，尋找α因子分解問題的減少。

6熱度

1回答

求證這組過一個無限字母表的所有語言是不可數

試圖做一些修改，但不知道在這一個： Prove that the set of all languages over a ﬁnite alphabet is uncountable. 我有一種感覺，這將需要使用Cantor Diagonalization方法 - 但我我不知道你會如何使用它來解決這個問題。

1熱度

2回答

Kolmogorov複雜度

如果有人能夠向我解釋柯爾莫哥洛夫複雜度是如何與隨機性和隨機投入相關的，我會感激不盡。另一件我不明白的事情 - 我們知道計算給定輸入X的Kolmogorov複雜性是不可判定的。既然如此，它怎麼可能是一種隨機性的衡量？感謝

2熱度

1回答

瞭解TM模擬器

我只是在看turing machine simulator code和整個下面的語句來到「帶地圖的時間和位置的符號。爲了計算符號，我們來看看在機器前面的一個步驟。如果此時頭部位於要求的位置，則該符號根據表格而改變，取決於相同位置處的以前的符號和機器所在的狀態。否則，符號不會改變。「斜體部分是什麼意思？要求的位置是什麼意思？