Finite Automata as a language acceptor and translator | Deterministic Finite Automata (DFA) | Nondeterministic Finite Automata(NFA) in Hindi

Unit 1

Introduction of Automata Theory

Topic 2 : Finite Automata as a language acceptor and translator

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

Deterministic Finite Automata (DFA)

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

Nondeterministic Finite Automata(NFA)

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 करने �...

Finite Automata as a language acceptor and translator | Deterministic Finite Automata (DFA) | Nondeterministic Finite Automata(NFA) in Hindi