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

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

non deterministic finite automata in hindi

Present State

Next State for Input 0

Next State for Input 1

a,b

a,c

b,c

NP Complete Problem in Hindi

NP-Complete problems एक महत्वपूर्ण वर्ग हैं जो computational complexity the...

Multihead Turing Machine और Multidimensional Turing Machine की विशेषताएँ और अंतर

Multihead Turing Machine एक प्रकार की Turing Machine है जिसमें एक से अ�...

Universal Turing Machine and Multitape in Hindi

Universal Turing Machine (UTM) एक ऐसी ट्यूरिंग मशीन है, जो किसी भ...

Techniques for Turing Machine Construction in Hindi

Turing Machine कंप्यूटर विज्ञान में एक theoretical model है, जो क�...

Petri Net Model in Hindi | Theory of Computation (TOC) Explained

Petri Net एक mathematical model है जो systems के behavior को graphically represent करने �...

Non Deterministic Finite Automata in Hindi (NDFA)