Non Deterministic Finite Automata in Hindi (NDFA)


Unit 2

Types of Finite Automata

 

Topic 1 :  Non Deterministic Finite Automata (NDFA)

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 किया सकता है जैसे _ 

  1. Non Deterministic Finite Automata with ε-moves 

  2. Finite State transducers\

  3. Pushdown Automata

  4. Alternating Automata, 

  5. ω-Automata

  6. 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).

non deterministic finite automata in hindi

 

   Present State
     Next State for Input 0
     Next State for Input 1
           a                      a,b                       b
           b                       c                     a,c
           c                     b,c                      c

 

Related Post