pushdown-automaton

0熱度

1回答

我在接近以下問題時遇到問題。給了以下語言的上下文無關文法： {x#y | x,y in {0,1}* and |x| != |y|} 什麼是解決這個問題的最佳方式是什麼？目前我只是用直覺來解決像這樣的問題，但是有沒有有用的技巧？也就是說，你能想出這種語言的PDA會是什麼樣子，然後從中得到語法嗎？有沒有使用語法A和B來查找語法G = A和B的方法？我很努力地看到如何解決這個問題，所以任何幫助

1熱度

1回答

證明一個帶有k個堆棧的PDA是圖靈識別的

這曾經是一個家庭作業，但我現在正在使用它進行修改;但是這個問題沒有解決辦法。任何意見將不勝感激。問題問：「讓一個k-PDA成爲一個可以訪問k堆棧的下推自動機，1-PDA是一個標準的PDA，你已經看到2-PDA可以識別任何圖靈可識別的語言。證明，對於任何k≥0，任何識別的語言都是圖靈識別的k-PDA。「直接複製&粘貼，有誰能幫助解決這個問題嗎？此外，我覺得這是寫錯了，但我不知道什麼是對的。

0熱度

1回答

FSM中的狀態應該與上下文類型成爲朋友嗎？

我已經構建了一個基於類的下推式自動機有限狀態機。上下文類（內部狀態被修改的類）有一些只有狀態才能訪問的方法（遞增/遞減某些迭代器，推/彈出狀態，設置接受狀態等）。目前他們是公開的，因爲不同的州需要訪問他們。將方法設置爲protected/private並將狀態定義爲上下文的朋友會更好嗎？（NB4「意見爲基礎的！」）

0熱度

1回答

下推自動機的結構問題

我認爲我的結構知識是缺乏的。我得到的錯誤如： pda.c:33:26: error: 'top' undeclared (first use in this function) if(pda.stack[top] == '\0') pda.c:54:7: error: 'accepted' undeclared (first use in this function) if(accepted ==

1熱度

1回答

Palindrones下推自動機

所以，我發現這個PDA接受語言{0,1} * palindromes。不過，我不理解它如何能接受 '1' 或 '0'。在B它可以讀取1或0並將相同的符號推入堆棧，然後轉至C。然而，一旦它出現在C中，它無處可去，需要讀取另一個符號才能在堆棧中達到$。有人可以解釋它是如何工作的？我在想，爲了接受一個符號，我們需要從B到D =>1,$->ε | 0,$->ε的轉換。我是否正確？謝謝:)

1熱度

1回答

下推自動放棄了α，β和γ串

我理解的PDA的基礎知識，但有一個，我還沒有碰到過before.The問題來的一個問題就是：考慮與最終狀態和空接受以下PDA中號疊加。 $ M =（K，\ Sigma，\ Gamma，\ delta，q_0，Z_0，F）$，$ K = q_0，\ Sigma = a，b，c，\ Gamma = a，b，c，S， Z_0 = S，F = q_0）$。過渡關係由， $ \增量（Q_0，\ε，S）=（

0熱度

1回答

想知道下推自動機解決方案是否正確

我有一個問題說：構建一個接受語言{a^i b^j | 0 < =我< = j的} ，這是給定的解決方案： δ (q0, a, z) = (q0, az) read a, push a δ (q0, a, a) = (q0, aa) δ (q0, b, a) = (q1, λ) read b, pop a δ (q1, b, a) = (q1, λ) δ (

0熱度

1回答

爲什麼文章中的這個問題不可能？

http://wiki.apidesign.org/wiki/Impossible 我看過這個，我不明白爲什麼這個問題似乎是不可能的。賦予「機器」的字符串總是有限的權利？因此，即使我有10億個零和10億個零，我們也可以輕鬆地編寫一個腳本，該腳本爲該字符串返回true或false（它將被正確接受）。另一個輸入可能是「00011」，使其無效。我可能在這裏不明白，但是這個問題對我來說似乎是「可編碼的

0熱度

1回答

PDA中的計數字母頻率

我正在嘗試構建一個PDA或CFG，它接受E是最常見字母的所有單詞。例如，奶酪和T恤就是用語言寫成的。我很確定這種語言是上下文無關的，但我似乎無法爲它構建PDA。這可能嗎？

-1熱度

1回答

與此PDA結構

在人類語言中掙扎：由分隔的單詞的列表（從構造「一」和'B的）「C的和存在於某些索引的至少一個字I的帶有多個字母‘a’在然後將其在索引字I + 2