Unknown
NFA Michael O. Rabin और Dana Scott के द्वारा 1959 में introduce किया गया था
NDFA में, एक Spacial input Symbol के लिए, Machine में states के किसी भी Combination को Move कर सकती है। दूसरे शब्दों में, Machine ले जाने के लिए Exact State Determined नहीं की जा सकती। Non Deterministic Finite Automata कहा जाता है। जैसा कि इसमें States की सीमित संख्या है, Machine को Non Deterministic Finite Machine या Non Deterministic Finite Automata कहा जाता है।
एक Non Deterministic Finite Automata (NDFA), या Non Deterministic Finite State Machine इन restrictions का पालन करने की आवश्यकता नहीं है। विशेष रूप से, प्रत्येक DFA भी एक NFA है। कभी-कभी NFA Word का उपयोग Narrower Sense में किया जाता है,
Subset Construction Algorithm का उपयोग करते हुए, प्रत्येक NFA को एक समान DFA में translate किया जा सकता है | यानी, एक formal language को पहचानने वाला DFA की तरह, NDFA केवल Regular Languages को पहचानते हैं।
NFA को कई तरीको से generalized किया सकता है जैसे _
Non Deterministic Finite Automata with ε-moves
Finite State transducers\
Pushdown Automata
Alternating Automata,
ω-Automata
Probabilistic Automata
Formal Definition :
NDFA को 5 tuple का उपयोग कर के define किया जाता है (Q, ∑, δ, q0, F)
Q : Finite set of states है
∑ : यह Finite set का symbol है | इसे alphabets कहते है
δ : यह Transition Function है (δ: Q × ∑ → 2Q)
Q0 : यह initial state है | जहा से input processed किया जाता है (q0 ∈ Q)
F : यह Set of Final state है | Q (F ⊆ Q).
Present State |
|
|
||
a | a,b | b | ||
b | c | a,c | ||
c | b,c | c |