dfa演算法

⑴ 有沒有師兄，師姐有關於DFA,BFS的題目，練練演算法 別太難

應該是DFS吧？DFA是編譯原理裡面的
練演算法推薦杭電ACM：
DFS：1010 1241 1312
BFS：1026 1242

⑵ 用C語言採用模擬DFA演算法編寫一個掃描器（詞法分析器）

（1）濾掉源程序中的無用成分，如空格；
這個」源程序「是指？不是只要識別像
bbbbaa+1,
aa-1
這樣的字元串么？

⑶ dfa的最小化如何化簡的步驟

下面具體介紹DFA的化簡演算法：
（1） 首先將DFA M的狀態劃分出終止狀態集K1和非終止狀態集K2。
K＝K1∪K2
由上述定義知，K1和K2是不等價的。
（2） 對各狀態集每次按下面的方法進一步劃分，直到不再產生新的劃分。
設第i次劃分已將狀態集劃分為k組，即：
K＝K1(i)∪K2(i)∪…∪Kk(i)
對於狀態集Kj(i)（j=1,2,…,k）中的各個狀態逐個檢查，設有兩個狀態Kj』、 Kj』』∈Kj(i)，且對於輸入符號a，有：
F（Kj'，a）＝Km
F（Kj''，a）＝Kn
如果Km和Kn屬於同一個狀態集合，則將Kj』和Kj』』放到同一集合中，否則將Kj』和Kj』』分為兩個集合。
（3） 重復第（2）步，直到每一個集合不能再劃分為止，此時每個狀態集合中的狀態均是等價的。
（4） 合並等價狀態，即在等價狀態集中取任意一個狀態作為代表，刪去其他一切等價狀態。
（5） 若有無關狀態，則將其刪去。
根據以上方法就將確定有限自動機進行了簡化，而且簡化後的自動機是原自動機的狀態最少的自動機。

⑷ 給出描述java表達式的DFA~~~~~~~~~~在線等

這是DFA演算法，自己設定好值，看下結果

import java.util.*;
import java.io.*;

class DFA
{
boolean recognizeString(int move[][], int accept_state[], String word)
{

int s=0;
for (int i = 0; i <word.length(); i++)
{
char c = word.charAt(i);
s = move[s][c - 'a'];
}
for (int j = 0; j < accept_state.length; j++)
if (s == accept_state[j]) return true;
return false;
}
public static void main(String args[]) throws IOException
{
int n, m;
BufferedReader in = new BufferedReader(new FileReader("DFA.in"));
StringTokenizer st = new StringTokenizer(in.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
while (n != 0)
{
int[][] move = new int[n][m];
for(int i=0; i<n; i++)
{
st = new StringTokenizer(in.readLine());
for (int j=0; j<m; j++)
move[i][j] = Integer.parseInt(st.nextToken());
}
String[] temp = in.readLine().split("\s");
int[] accept = new int[temp.length];
for (int i=0; i<accept.length; i++) accept[i] = Integer.parseInt(temp[i]);
String word = in.readLine();
while (word.compareTo("#") != 0)
{
DFA dfa = new DFA();
if (dfa.recognizeString(move, accept, word)) System.out.println("YES"); else System.out.println("NO");
word = in.readLine();
}
st = new StringTokenizer(in.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
}
}
}

⑸ 用C語言採用模擬DFA演算法編寫一個掃描器（詞法分析器），用來識別：由任意個a或b開始後接aa再自加或自減1的

你是什麼意思啊，告訴我才知道啊，是不是漏字了

⑹ 有多個初始狀態的 DFA

對於多正則表達式匹配（Multiple Regular Expression Matching）的 DFA
在創建多正則表達式匹配的 DFA 的過程中，就有一個 DFA 的 Union 操作，在這個過程中，如果狀態膨脹失去控制，需要使用某種方式對正則表達式集合進行分組，以便抑制這種狀態膨脹。分組後會生成多個 DFA ，但是為了應用程序介面方便統一，將這多個 DFA 揉進一個 DFA 對象，每個分組的 DFA 就需要一個不同的初始狀態(根)。
改善 DFA Union 的性能
有相同 Tail 的多個 DFA
如果用 adfa_build 分別創建了多個不同的 ADFA(Acyclic DFA, 無環自動機)，在隨後的某個時間點，想將這多個 ADFA 進行合並，仍然是 DFA 的 Union 操作，這種情況下 NFA 轉 DFA 過程中的狀態膨脹總是線性的，雖然如此，NFA 轉 DFA 的過程中仍然需要大量內存。

雖然之前我也曾想過 DFA 包含多個初始狀態(根)的可能性，但一直沒有深入思考，這次經過仔細思考，發現：對於(所有的) DFA 最小化演算法，從理論上講，完全沒有必要限制為單根 DFA，不管有多少個根，演算法都能正常工作！唯一需要注意的是，最小化前後的根，在某些應用中需要一一對應起來。
最小化之前的多根 DFA 可以完全是獨立的，唯一的要求是所有 DFA 的狀態 ID 屬於同一個 ID 空間，這很簡單，工程上用同一個 DFA 對象來表達即可，對於 分離的多個 DFA 對象，只需要實現一個 DFA 包裝器，將多個分離的 DFA 的狀態 ID 重新映射即可。
如此，就完成了執行多根 DFA 最小化的所有準備。最小化完成之後，這些多個 DFA 會共享一些相同的尾部，一般情況下，頭部不會共享；不過極端情況下，例如 DFA1 是 DFA2 的子集，那麼，從 DFA2 的根就能到達 DFA1 的根，此時整個 DFA1 就被完全共享了。
執行 DFA Union
所有的尾部都被最小化了，然後再用 NFA 轉化 DFA 的方式執行最小化，這樣，大大減小了 NFA 轉 DFA 的時間和內存消耗。

動態 DFA 匹配多個正則表達式
細節可參考：多正則表達式匹配 (Multiple Regular Expression Matching) 中的動態 DFA 演算法
主要有兩點：

多個子 DFA 在 regex_build 時使用最小化演算法得到一個包含多個根，一個尾的 DFA
動態 DFA 是多個子 DFA 的並集，因為並集的完全 DFA 無法構造出來（狀態的指數爆炸），動態地從DFA並集的NFA構造並集的部分DFA
用正則表達式集合的並集的動態DFA搜索到具體匹配的正則表表達式ID之後，從該ID的根出發，去抽取括弧部分
實現
在實現這個概念的過程中，對我的 adfa_minimize 做了一些重構，同時也進行了一些優化。

⑺ 編譯原理中，由NFA轉化來的DFA是唯一的嗎

根據演算法轉化來的DFA肯定是唯一的，但是轉化得到的DFA並不一定是狀態最少的，每一個DFA都可以轉化到狀態最少的DFA。狀態最少的DFA是唯一的（狀態名不同的同構情況除外）。可參考龍書（一本編譯書籍）。因為每個DFA都可以對應相應的NFA（DFA本身就是），所以NFA轉化的DFA不一定都是狀態數最少的。

⑻ nfa如何轉換成等價的dfa結果唯一嗎

nfa轉化成等價的dfa結果是不唯一的
NFA轉化成等價的DFA再轉化成最簡化的DFA結果是唯一的
將NFA轉化成等價的DFA有一套固定的演算法，這里空間有限我不贅述，你可以去網路「NFA轉化成DFA
演算法」

⑼ 編譯原理NFA轉DFA ，請問DFA的初始狀態如何確定

NFA確定化的時候，包含NFA初態的那個DFA狀態就是確定後的DFA的初態。

DFA的終態就是所有包含了NFA終態的DFA的狀態。

對於DFA來說，他的初態就是包含了NFA唯一初態1的那個狀態，就是左邊的1，2右邊的1了。

脫氧核糖-磷酸鏈在螺旋結構的外面，鹼基朝向裡面。兩條多脫氧核苷酸鏈反向互補，通過鹼基間的氫鍵形成的鹼基配對相連，形成相當穩定的組合。

(9)dfa演算法擴展閱讀：

將DNA或RNA序列以三個核苷酸為一組的密碼子轉譯為蛋白質的氨基酸序列，以用於蛋白質合成。密碼子由mRNA上的三個核苷酸（例如ACU，CAG，UUU）的序列組成，每三個核苷酸與特定氨基酸相關。

例如，三個重復的胸腺嘧啶（UUU）編碼苯丙氨酸。使用三個字母，可以擁有多達64種不同的組合。由於有64種可能的三聯體和僅20種氨基酸，因此認為遺傳密碼是多餘的（或簡並的）：一些氨基酸確實可以由幾種不同的三聯體編碼。

但每個三聯體將對應於單個氨基酸。最後，有三個三聯體不編碼任何氨基酸，它們代錶停止（或無意義）密碼子，分別是UAA，UGA和UAG 。