dfa概念問題

brotherofninth

小弟就快考試對其他野都還可以，唯獨dfa就真係唔明，有無師兄指點下

就我所知，dfa就係將nfa路徑限制，有需要就狀態整合，對我嚟講就極抽象，wiki/youtube/note都睇過，就係唔知咩時候要整合，依基本上靠估

以依條題目為例:

L0

X-----a----b-----c
A0---S0---S0---S0
F0---S0---F0---S0
S0---F0---F0---F0

L1

X----a----b----c
A1---A1--A1---F1
F1---F1---F1---F1
S1---F1---F1---A1

已知starting state 係(S0,S1)

叫我L0 n L1

我剩係寫到

X---------------a------------b------------c
A1,A0--------A1,S0-------A1,S0------ F1,S0
F1,F0---------F1,S0-------F1,F0-------F1,S0
S1,S0---------F1,F0-------F1,F0------ A1,F0

chi251155

http://stackoverflow.com/questio ... tic-finite-automata
第一步改個好啲既名，由q0到qn
第二步將其中一個dfa入面既state改名，改到兩個dfa既state啲名冇重複
第三步由starting state開始，寫番個新既dfa出黎
條link入面有例子

brotherofninth

第一步改個好啲既名，由q0到qn
第二步將其中一個dfa入面既state改名，改到兩個dfa既state啲名冇重複
第三 ...
chi251155 發表於 2015-4-23 23:20

神

你咁講就明

咁nfa to dfa有咩方法

brotherofninth

第一步改個好啲既名，由q0到qn
第二步將其中一個dfa入面既state改名，改到兩個dfa既state啲名冇重複
第三 ...
chi251155 發表於 2015-4-23 23:20

跪求解答我第二題

chi251155

回覆 4# brotherofninth


    nfa轉dfa太難講
由q0開始，你要搵e-closure(q0)，即係由q0一路跟住e行到所有既state。
下一步就將e-closure(q0)成為個dfa既starting state q0*.
咁當你既alphabet係{a, b}，你要搵由q0*入面所有既state行a既所有可能，假設{ q0, q1, q3, q5 }咁樣。如果呢個set同q0*唔一樣，就要改個新名q1*。跟住做b，做到冇哂路可以行為止。
新既dfa入面，其中有包括nfa入面個final state既就係dfa既final state。
可以參考下呢個
http://web.cecs.pdx.edu/~harry/compilers/slides/LexicalPart3.pdf

brotherofninth

回覆  brotherofninth


    nfa轉dfa太難講
由q0開始，你要搵e-closure(q0)，即係由q0一路跟住e行到所有 ...
chi251155 發表於 2015-4-25 11:08

    感激明咗八，九成