Unknown
Finite Automata (FA) pattern को पहचानने की सबसे सरल machine है। Finite Automata या Finite state machine एक abstract machine है जिसमें पाँच tuple होते हैं। इसमें एक state से दूसरे state में जाने के लिए state और rules का एक सेट है, लेकिन यह लागू input symbol पर निर्भर करता है। मूल रूप से यह Digital computer का एक abstruct model है। निम्नलिखित आंकड़ा एक सामान्य Automata की कुछ आवश्यक विशेषताएं दिखाता है।
Finite Automata के 5 tuple
Q : इसे finite set of states कहते है
∑ : यह finite set का symbol है इसे automaton की वर्णमाला (alphabet) कहा जाता है
δ : यह एक transition function है
q0 : यह प्रारम्भिक अवस्थ है जहा से input processed किया जाता है (q0 ∈ Q).
F : F final state का set है Q (F ⊆ Q).
Finite Automata 2 Type के होते है
1. Deterministic Finite Automata (DFA)
2. Nondeterministic Finite Automata(NFA)
Deterministic Finite Automata (DFA) :
DFA deterministic finite automata को संदर्भित (Referenced) करता है। deterministic Computation की विशिष्टता (specialty) को संदर्भित (Referenced) करता है। अगर machine को एक बार में एक input string पढ़ा जाता है तो finite automata को deterministic finite automat कहा जाता है।
DFA में, वर्तमान स्थिति से अगले state तक specialty input के लिए केवल एक ही रास्ता है।
DFA null move को स्वीकार नहीं करता है, अर्थात, DFA किसी भी input character के बिना state नहीं बदल सकता है।
DFA में कई अंतिम अवस्थाएँ हो सकती हैं। इसका उपयोग Compiler में Lexical Analysis में किया जाता है।
DFA 5 tuples का collection होता है
Q : इसे finite set of states कहते है
∑ : यह finite set का symbol है इसे automaton की वर्णमाला (alphabet) कहा जाता है
δ : यह एक transition function है
q0 : यह प्रारम्भिक अवस्थ है जहा से input processed किया जाता है (q0 ∈ Q).
F : F final state का set है Q (F ⊆ Q).
2.Nondeterministic Finite Automata(NFA) :
NDFA में, एक विशेष input symbol के लिए, machine state के किसी भी combination को स्थानांतरित (Move) कर सकती है। दूसरे शब्दों में, machine द्वारा ले जाने के लिए सटीक स्थिति निर्धारित नहीं की जा सकती। इसलिए, इसे Nondeterministic Finite Automata कहा जाता है। जैसा कि इसमें states की सीमित संख्या है, machine को Nondeterministic Finite machine या Nondeterministic Finite Automata(NFA) कहा जाता है।
NDFA में 5 tuple represent किये जाते है
Q : इसे finite set of states कहते है
∑ : यह finite set का symbol है इसे automaton की वर्णमाला (alphabet) कहा जाता है
δ : यह एक transition function है
q0 : यह प्रारम्भिक अवस्थ है जहा से input processed किया जाता है (q0 ∈ Q).
F : F final state का set है Q (F ⊆ Q).