finite-automata

0熱度

2回答

有K個狀態的NFA接受字符串的長度<= k

是否有可能構造一個N狀態，其中k個狀態可識別所有長度爲< = k的字符串並拒絕長度大於k的所有字符串？

0熱度

1回答

當r和r的DFA被確定時，發現r *的DFA

我想要說明當定義r的r和DFA時，找到r *的DFA的方法的例子。以及如何思考？我讀了一本教科書，但我不明白。謝謝。

1熱度

2回答

證明具有k <2^n個狀態的任何DFA不接受具有奇數個字符的字符串

讓語言L_n具有字符集Sigma = {a_1，...，a_n}。 L_n恰好包含那些包含一些奇數次字符的單詞。等價地，如果L_n^i是每個包含奇數個a_i的字的語言，則L_n = L_n^1 union ... union L_n^n。我已經產生了接受L_n和2^n狀態的DFA的NFA，我現在需要證明這是接受此語言的最小DFA。我給出的提示假設有爲k < 2^n種狀態，它接受L_N的DFA，

1熱度

1回答

讓A，B，C成爲時尚。考慮方程X = AX + BX + C。解答X必須是時尚嗎？

讓A，B，C成爲時尚。考慮方程X = AX + BX + C。解答X必須是時尚嗎？你能幫我解決這個問題嗎？ fad是一種常用語言

2熱度

1回答

DFA可以識別多少種語言？

根據Sipser的「計算理論導論」：如果A是機器M接受的所有字符串的集合，我們說A是機器M的語言並且寫L（M）= A。 M識別A ...機器可以接受多個字符串，但它總是隻識別一種語言。以及我們說M如果A = {w | M接受w}。我猜這個問題已經被回答了，但是我想知道是否有人有任何想法，如果有什麼有趣的話我們可以說關於常規語言的子集，如果我們可以說，原始DFA可以識別它們，並且原始DFA與識別

2熱度

1回答

DFA構造爲L = {（NA（w）的-nb（W））模3> 0}

作爲每標題： L = {（N 一個（W）-n b （W））模3> 0} 字母表= {A，b} 我發現兩個答案，這一問題：在這種所以我們的語言被接受。然而， w = b 被接受爲好。在未來的解決方案：我們的 w = b 問題在這裏解決，但 w = aaab 是不能接受的。我該如何解決這個問題？我無法在互聯網上找到合適的答案。

2熱度

1回答

從字母{a，b，c}構建DFA

在字母{a，b，c}上構建一個DFA，接受具有三個連續相等字母的所有字符串的集合。因此，它可以接受：AAA，BBB，CCC，AB | BB，caaac，ccbbbcc，aaabbbc .. 我已經嘗試了很多不同的方式，這是一個巨大的圖我在想，如果有一個更優雅的方式在做這個嗎？

1熱度

1回答

理論：怎麼能是這是從計算書的理論採取機M1

識別的語言：如果下面的圖表示機器M1，怎麼能A，語言機器M1識別，描述爲： A = {w |當字符串011被機器M1接受時，w包含至少一個1和偶數個0，後面跟着最後一個} 。 011實際上包含至少一個1，但偶數個0不跟隨最後1. 然後，說「和偶數個0跟隨最後1」是不是不正確？

0熱度

1回答

是基於有限自動機還是遞歸回溯的v8/firefox RegExp實現？

我遇到了這個文檔：https://swtch.com/~rsc/regexp/regexp1.html 聲稱Perl，Java和許多其他語言使用基於遞歸回溯的「慢」RegExp，但grep和awk（也是Go）使用更快的有限自動機。即正則表達式轉換爲FA然後執行。該論文還聲稱，所有語言都應該切換到FA技術，儘管其實施更爲複雜。我很好奇，如果當前的JavaScript實現有這樣或那樣的方式。

0熱度

1回答

DFA中的空間含義？

這是由工具生成的DFA的正則表達式（A | B）* abaabb（A | B）* 什麼是空間中的圖片是什麼意思？你認爲這是完全正確的，因爲它沒有顯示字符串abaabb的其他可能性。例如如果字符串中間的b得到a，該怎麼辦？