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).
Present State |
|
|
||
a | a,b | b | ||
b | c | a,c | ||
c | b,c | c |
Related Post
- What is Automata machine in hindi | Examples of automata machines
- Finite Automata as a language acceptor and translator | Deterministic Finite Automata (DFA) | Nondeterministic Finite Automata(NFA) in Hindi
- What is Moore machines and mealy machines in Hindi
- What is Turing machine (composite machine) in toc in hindi
- Conversion from Mealy to Moore and vice versa in Hindi
- Non Deterministic Finite Automata in Hindi (NDFA)
- Deterministic Finite Automaton in Hindi (DFA) | Deterministic Finite-State Machine (DFSM)
- Conversion of NDFA to DFA in Hindi
- Arden's Theorem in TOC in Hindi
- Minimization of DFA in Hindi (Minimization of Automata Machines)
- Regular Expression in TOC in Hindi
- Union process in DFA | What is Union process in TOC
- Intersection of Finite Automata in Hindi
- Properties of Context Free Languages Hindi
- Two-way Deterministic Finite Automaton (2DFA) in Hindi
- Types of Grammar in TOC in Hindi | Chomsky Hierarchy in Theory of Computation
- Derivation Tree in TOC in Hindi
- Ambiguity in Grammar in TOC in Hindi
- Simplification of context free grammar in Hindi
- Conversion of grammar to automata machine and vice versa in Hindi
- Chomsky normal form and Greibach normal form in hindi
- What is Pushdown Automata in TOC in Hindi
- Example of PDA in Hindi | Example of Pushdown Automata in Hindi
- Deterministic pushdown automaton And Non-Deterministic pushdown automaton in Hindi
- Conversion of PDA Into Context Free Grammar and Vice Versa | PDA in TOC in hindi | Push Down Automata in Hindi | Context Free Grammar in Hindi
- CFG equivalent to PDA in hindi | context free grammar equivalent to push down automata in hindi | toc tutorial in hindi | theory of computation in hindi