dfa概念問題

本帖最後由 brotherofninth 於 2015-4-23 17:10 編輯

小弟就快考試對其他野都還可以,唯獨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

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

TOP

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



你咁講就明

咁nfa to dfa有咩方法

TOP

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

跪求解答我第二題

TOP

回覆 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

TOP

回覆  brotherofninth


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


    感激明咗八,九成

TOP