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)

Related Post