नियतात्मक परिमित ऑटोमेटन
Finite Automaton को दो प्रकारों में वर्गीकृत किया जा सकता है -
- निर्धारक परिमित ऑटोमेटन (DFA)
- गैर-नियतात्मक परिमित ऑटोमेटन (NDFA / NFA)
निर्धारक परिमित ऑटोमेटन (DFA)
डीएफए में, प्रत्येक इनपुट प्रतीक के लिए, कोई व्यक्ति यह निर्धारित कर सकता है कि मशीन किस ओर जाएगी। इसलिए, इसे कहा जाता हैDeterministic Automaton। जैसा कि इसमें राज्यों की एक सीमित संख्या है, मशीन कहा जाता हैDeterministic Finite Machine या Deterministic Finite Automaton.
DFA की औपचारिक परिभाषा
एक डीएफए का प्रतिनिधित्व 5-ट्यूपल (क्यू, δ, represented, q 0 , F) द्वारा किया जा सकता है जहां -
Q राज्यों का एक समुच्चय है।
∑ वर्णमाला नामक प्रतीकों का एक परिमित समुच्चय है।
δ वह संक्रमण क्रिया है जहाँ δ: Q ×। → Q
q0वह प्रारंभिक अवस्था है जहां से किसी भी इनपुट को संसाधित किया जाता है (q 0 ) Q)।
F अंतिम स्थिति / Q (F। Q) के राज्यों का एक समूह है।
एक डीएफए का चित्रमय प्रतिनिधित्व
DFA को डिग्राफ्स द्वारा दर्शाया जाता है state diagram।
- कोने राज्यों का प्रतिनिधित्व करते हैं।
- इनपुट वर्णमाला के साथ लेबल किए गए आर्क्स संक्रमण को दर्शाते हैं।
- प्रारंभिक अवस्था को एक खाली आवक चाप द्वारा निरूपित किया जाता है।
- अंतिम अवस्था को दोहरे वृत्तों द्वारा इंगित किया जाता है।
उदाहरण
एक नियत परिमित ऑटोमोटन होने दें →
- क्यू = {ए, बी, सी},
- , = {0, 1},
- q 0 = {a},
- एफ = {सी}, और
संक्रमण कार्य δ जैसा कि निम्नलिखित तालिका द्वारा दिखाया गया है -
| वर्तमान स्थिति | इनपुट के लिए अगला राज्य 0 | इनपुट के लिए अगला राज्य 1 |
|---|---|---|
| a | ए | ख |
| b | सी | ए |
| c | ख | सी |
इसका ग्राफिकल प्रतिनिधित्व इस प्रकार होगा -
