Unknown
Automata Word Greek language के word αὐτόματα से लिया गया है | जिसका अर्थ आत्म-अभिनय (self-acting) होता है | एक automaton एक abstract self-propelled computing device होता है | जिसका उपयोग कर के computational problums को हल किया जाता है | जो automatically एक predetermined sequence का अनुसरण करता है | यदि किसी automaton में finite number of states है तो वह Finite Automaton (FA) और Finite State Machine (FSM). कहलाता है
Automaton को 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).
Finite input :
एक automaton जिसमे केवल finite sequence के symbols accepts किये जाते है
Infinite input :
एक automaton जो केवल Infinite word accepts करता है ऐसे automata को ω-automata कहा जाता है |
Tree word input :
इसमें sequence of symbols की जगह tree of symbols होता है प्रत्येक symbol को पढ़ने के बाद इस मामले में automaton input tree successor symbols को पढ़ता है | यह कहा जाता है की automaton प्रत्येक successor (उत्तराधिकारी) के लिए स्वंय की एक copy बनता है | इस तरह के automaton को tree automaton कहा जाता है
Infinite tree input :
ऊपर दिए गए दो extensions को combinedकिया जा सकता है, इसलिए automaton एक tree की संरचना को परिमित शाखाओं के साथ पढ़ता है। इस तरह के एक automaton को एक Infinite tree कहा जाता है
एक automaton जिसमे states की सिमित संख्या होती है
Infinite states :
एक automaton जिसमे states की सिमित सख्या या states की संख्या भी नहीं हो सकती है
Classes of automata
Finite state machine (FSM)
Deterministic pushdown automaton (DPDA)
Pushdown automaton (PDA)
Linear bounded automaton (LBA)
Turing machine