文件名称:NFA-to-DFA
介绍说明－－下载内容均来自于网络，请自行研究使用
Theory:
NDFA: It is a mathematical model containing 5 tuples
a) Q- finite non empty set elements of which are called as state.
b) T- set of alphabets.
c) δ- is a mapping function Q*{T {λ}}*2Q
d) S-start state i.e. S ε Q
e) F- F (subset) Q and F is a final state.
DFA: A finite automata is called DFA if
a) There is no transition for function λ.
b) For each state S and a input symbol ‘a’, there is at most one edge with a symbol ‘a’ leaving from S.
Algorithm:
1. Convert the given NDFA into state transition table where each state corresponds to a row and each input symbol corresponds to a column.
2. Construct the successor table(ST) which lists subset of state reachable from set of initial state
3. The transition graph given by the ST in the required DFA if possible reduces the number of state.
Eg:
NFA:
δ a b
qo q1 q2
q1 - q0
q2 [q0q1] -
DFA:
δ a b
qo q1 q2
q1 - q0
q2 [q0q1] -
[q0q1] q1 [q2q0]
[q2q0] [q0q1] q2-Theory:
NDFA: It is a mathematical model containing 5 tuples
a) Q- finite non empty set elements of which are called as state.
b) T- set of alphabets.
c) δ- is a mapping function Q*{T {λ}}*2Q
d) S-start state i.e. S ε Q
e) F- F (subset) Q and F is a final state.
DFA: A finite automata is called DFA if
a) There is no transition for function λ.
b) For each state S and a input symbol ‘a’, there is at most one edge with a symbol ‘a’ leaving from S.
Algorithm:
1. Convert the given NDFA into state transition table where each state corresponds to a row and each input symbol corresponds to a column.
2. Construct the successor table(ST) which lists subset of state reachable from set of initial state
3. The transition graph given by the ST in the required DFA if possible reduces the number of state.
Eg:
NFA:
δ a b
qo q1 q2
q1 - q0
q2 [q0q1] -
DFA:
δ a b
qo q1 q2
q1 - q0
q2 [q0q1] -
[q0q1] q1 [q2q0]
[q2q0] [q0q1] q2
NDFA: It is a mathematical model containing 5 tuples
a) Q- finite non empty set elements of which are called as state.
b) T- set of alphabets.
c) δ- is a mapping function Q*{T {λ}}*2Q
d) S-start state i.e. S ε Q
e) F- F (subset) Q and F is a final state.
DFA: A finite automata is called DFA if
a) There is no transition for function λ.
b) For each state S and a input symbol ‘a’, there is at most one edge with a symbol ‘a’ leaving from S.
Algorithm:
1. Convert the given NDFA into state transition table where each state corresponds to a row and each input symbol corresponds to a column.
2. Construct the successor table(ST) which lists subset of state reachable from set of initial state
3. The transition graph given by the ST in the required DFA if possible reduces the number of state.
Eg:
NFA:
δ a b
qo q1 q2
q1 - q0
q2 [q0q1] -
DFA:
δ a b
qo q1 q2
q1 - q0
q2 [q0q1] -
[q0q1] q1 [q2q0]
[q2q0] [q0q1] q2-Theory:
NDFA: It is a mathematical model containing 5 tuples
a) Q- finite non empty set elements of which are called as state.
b) T- set of alphabets.
c) δ- is a mapping function Q*{T {λ}}*2Q
d) S-start state i.e. S ε Q
e) F- F (subset) Q and F is a final state.
DFA: A finite automata is called DFA if
a) There is no transition for function λ.
b) For each state S and a input symbol ‘a’, there is at most one edge with a symbol ‘a’ leaving from S.
Algorithm:
1. Convert the given NDFA into state transition table where each state corresponds to a row and each input symbol corresponds to a column.
2. Construct the successor table(ST) which lists subset of state reachable from set of initial state
3. The transition graph given by the ST in the required DFA if possible reduces the number of state.
Eg:
NFA:
δ a b
qo q1 q2
q1 - q0
q2 [q0q1] -
DFA:
δ a b
qo q1 q2
q1 - q0
q2 [q0q1] -
[q0q1] q1 [q2q0]
[q2q0] [q0q1] q2
(系统自动生成,下载前可以参看下载内容)
下载文件列表
NFA to DFA.c