可計算性：在P中接受長度單詞的DFA的語言是什麼？

我一直在努力與這一段時間，我不能拿出任何東西。任何指針將非常感激。可計算性：在P中接受長度單詞的DFA的語言是什麼？

問題是：鑑於所有隻接收均勻長度字的DFA的語言，證明它是否在P中。

我已經考慮過製作一個圖靈機器，它可以像BFS/Dijkstra算法那樣遍歷給定的DFA，以便找到從開始狀態到接受狀態的所有路徑，但不知道如何處理循環？

謝謝！

來源

2011-12-19 user1105415

我認爲這是在P，在最差的二次方。的DFA中的每一個狀態可以有四個校驗規定

未訪問 - 狀態0
已知在奇數的步驟可達 - 狀態1
可達性未知在偶數的步驟 - 狀態2
已知兩種抵達，奇數和偶數的步驟號碼 - 狀態3

標記所有狀態爲未訪問，把起始狀態在隊列（FIFO，優先級，無論），將其奇偶校驗狀態設置爲2.

child_parity(n) 
    switch(n) 
     case 0: error 
     case 1: return 2 
     case 2: return 1 
     case 3: return 3 

while(queue not empty) 
    dfa_state <- queue 
    step_parity = child_parity(dfa_state.parity_state) 
    for next_state in dfa_state.children 
     old_parity = next_state.parity_state 
     next_state.parity_state |= step_parity 
     if old_parity != next_state.parity_state // we have learnt something new 
      add next_state to queue // remove duplicates if applicable 
for as in accept_states 
    if as.parity_state & 1 == 1 
     return false 
return true

除非我忽視的東西，每個DFA狀態在處理最兩次，每次檢查最多size孩子所需的操作。

來源

2011-12-19 17:02:16

這似乎只需要兩個狀態。

您的輸入狀態是空字符串，並且也是一個接受狀態。向字符串添加anythign會將其移動到下一個狀態，我們可以將其稱爲「奇怪」狀態，而不是使其成爲接受狀態。添加另一個字符串會使我們回到原始狀態。

我想我不再確定語言是否在P中，所以如果你給了我一個定義，那麼我可以告訴你它是否適合它，但這是最簡單的DFA之一大約...

來源

2011-12-19 07:29:26 corsiKa

謝謝你的時間！不幸的是，這個問題不是關於實際構建接受/所有/甚至是長度單詞的DFA，而是要確定給定的DFA是否只接受長度均勻的單詞 – user1105415 2011-12-19 07:36:33

我現在看到了您的問題。那麼我可以問，P語言的定義究竟是什麼？與P有關嗎？我只見過它在時間和計算上的複雜性，並且說實話，一旦你失敗了，你就沒有多用這個課程:) – corsiKa 2011-12-19 07:43:14

可計算性：在P中接受長度單詞的DFA的語言是什麼？

回答

相關問題