परिमित राज्य मशीनें। डीकेए लिखना

यदि आपने कभी अपने बॉट, एक वार्ताकार, संचार प्रोटोकॉल के एक दुभाषिया, और इस तरह से लिखने की कोशिश की, तो आप शायद परिमित राज्य मशीनों के पार आए। यह विषय, सिद्धांत रूप में, बहुत मुश्किल नहीं है, लेकिन अगर अचानक आपके पास "ऑटोमेटा के सिद्धांत" में एक कोर्स नहीं था, तो आपको बिल्ली का स्वागत है।

आज हम एक सरल निर्धारक परिमित राज्य मशीन बनाने का प्रयास करेंगे। मैं अचानक इसे पर्ल में लिखना चाहता था, लेकिन चूंकि हम किसी विशिष्ट चाल का उपयोग नहीं करेंगे, इसलिए सामान्य अवधारणा को किसी अन्य अनिवार्य भाषा में स्थानांतरित करना मुश्किल नहीं होगा।

परिचय

हम सिद्धांत में गहराई से नहीं जाएंगे, इसके लिए विशेष साहित्य, Google और विकिपीडिया;) हैं। आधार पर ही विचार करें। आइए देखें कि एक राज्य मशीन क्या है।

इलेक्ट्रॉनिक्स में, और प्रोग्रामिंग में, सबसे सरल मामले में हम तथाकथित "स्विचिंग फ़ंक्शन" के साथ काम कर रहे हैं। यह अपनी स्मृति के बिना एक अपेक्षाकृत आदिम अमूर्त है: हमारे पास इनपुट के लिए एक तर्क है, इसका आउटपुट के लिए एक मूल्य है। आउटपुट मान हमेशा केवल इनपुट पर निर्भर करता है।

और अगर हमें पिछले पर निर्भर होने के लिए फ़ंक्शन के अगले मूल्य की आवश्यकता है? कुछ पिछले वाले से? यहाँ हम पहले से ही अपनी स्मृति के साथ एक निश्चित अमूर्त में आते हैं। यह मशीन होगी। मशीन पर आउटपुट मूल्य इनपुट मूल्य और मशीन की वर्तमान स्थिति पर निर्भर करता है।

एक राज्य मशीन को तदनुसार इसलिए कहा जाता है क्योंकि उसके आंतरिक राज्यों की संख्या परिमित है। और, शायद, राज्य मशीनों का सबसे सरल निर्धारक है: प्रत्येक इनपुट सिग्नल के लिए केवल एक राज्य है जिसमें मशीन वर्तमान से जा सकती है।

इस प्रकार, हमारी मशीन निम्नलिखित द्वारा निर्धारित की जाती है:

• प्रारंभिक स्थिति;
• इनपुट वर्णमाला (संभावित इनपुट संकेतों का एक सेट);
• कई शर्तें;
• और रूपांतरण तालिका।

वास्तव में मशीन का पूरा सार अंतिम पैराग्राफ द्वारा निर्धारित किया जाता है। संक्रमण तालिका (एक संक्रमण आरेख के रूप में भी दिखाया गया है) में 3 कॉलम होते हैं: इनपुट संकेत (प्रतीक), वर्तमान स्थिति, अगली स्थिति। सब कुछ उदाहरण से स्पष्ट हो जाएगा।

आधार वर्ग

इसलिए, हम अपने आधार वर्ग को लागू करते हैं। हमने पहले ही तय कर लिया है कि हमें प्रारंभिक अवस्था, वर्तमान स्थिति और संक्रमण तालिका की आवश्यकता है। इनपुट वर्णों की वर्णमाला कार्य द्वारा निर्धारित की जाती है, इसलिए हमें इनपुट को सामान्य (सरल) करने की भी आवश्यकता है। उत्पादन संकेतों को वंशज वर्ग के निष्पादन योग्य तरीकों द्वारा किया जाएगा। हमारे जीवन को सरल बनाने के लिए, कृत्रिम रूप से "*" को वर्णमाला में जोड़ दें - कोई अन्य प्रतीक।

package FSM; use strict; use Carp; use vars qw($AUTOLOAD); # Create new object sub new { my $self = {}; my ($proto, $initial) = @_; my $class = ref($proto) || $proto; # Init ourselves $self->{INITIAL} = $initial; $self->{CURRENT} = $initial; $self->{STATES} = {}; bless ($self, $class); return $self; } sub setInitialState { my ($self, $initial) = @_; $self->{INITIAL} = $initial; return $self; } sub setCurrentState { my ($self, $current) = @_; $self->{CURRENT} = $current; return $self; } sub getCurrentState { my ($self, $current) = @_; return $self->{CURRENT}; } sub reset { my $self = shift; $self->{CURRENT} = $self->{INITIAL}; return $self; } sub addState { my $self = shift; my %args = @_; $self->{STATES}->{$args{STATE}}->{$args{SYMBOL}} = {NEXT => $args{NEXT}, ACTION => $args{ACTION}}; return $self; } sub removeState { my $self = shift; my %args = @_; if (exists $args{SYMBOL}) { delete $self->{STATES}->{$args{STATE}}->{$args{SYMBOL}}; } else { delete $self->{STATES}->{$args{STATE}}; } return $self; } # Be sure to override in child sub normalize { my ($self, $symbol) = @_; my $ret = {}; $ret->{SYMBOL} = $symbol; return $ret; } sub process { my ($self, $rawSymbol) = @_; my $state = $self->{STATES}->{$self->{CURRENT}}; $rawSymbol = $self->normalize($rawSymbol); my $symbol = $rawSymbol->{SYMBOL}; print STDERR "Current state " . $self->{CURRENT} . ", got symbol " . $symbol . "\n"; if (!exists $state->{$symbol} && exists $state->{'*'}) { print STDERR "Unrecognized symbol " . $symbol . ", using *\n"; $symbol = "*"; } # Do some action! $state->{$symbol}->{ACTION}($self, $rawSymbol) if ref $state->{$symbol}->{ACTION}; # Switch state if (exists $state->{$symbol}->{NEXT}) { $self->{CURRENT} = $state->{$symbol}->{NEXT}; } else { die "Don't know how to handle symbol " . $rawSymbol->{SYMBOL}; } return $self; } 1; 

मेरा मानना ​​है कि सभी तरीकों के नाम अपने लिए बोलते हैं। शायद यह सामान्य करने और प्रक्रिया के तरीकों पर ध्यान देने योग्य है। पहला इनपुट स्ट्रिंग को हैश में परिवर्तित करता है जिसमें SYMBOL फ़ील्ड होती है जिसमें एक इनपुट प्रतीक होता है जो ऑटोमेटन की वर्णमाला को सरल बनाता है। और प्रक्रिया वास्तव में राज्यों के बीच संक्रमण प्रक्रियाओं की "क्लॉकिंग", अगले सिग्नल को संसाधित करती है।

हम संक्षेप में समीक्षा करेंगे कि यह कैसे काम करता है। कक्षा का दिल स्टेट्स शाखा तालिका है, जो कि हैश का हैश हैश :)। यहां विचार सरल है, पहले स्तर पर हमारे पास राज्यों (STATE) और उनसे जुड़ी विशेषताओं की एक सूची है। चूंकि संक्रमण केवल इनपुट प्रतीक (SYMBOL) द्वारा निर्धारित किया जाता है, तदनुसार, ये विशेषताएँ ऐसे संकेत होंगे जो वास्तव में इस राज्य के लिए मान्य हैं। खैर, संकेत से, हम पहले से ही अगले राज्य (NEXT) को निर्धारित कर सकते हैं और, उपांग में, क्रिया (कार्रवाई), जो कि विधि का एक संदर्भ है।

यानी प्रक्रिया से, हम पहले इनपुट स्ट्रिंग ( सामान्यकृत ) से इनपुट वर्णमाला के चरित्र को प्राप्त करते हैं, फिर हम वर्तमान स्थिति को राज्यों की सूची से प्राप्त करते हैं। देखें कि क्या आने वाला चरित्र इसके लिए परिभाषित है। यदि परिभाषित नहीं किया गया है, तो हम मानते हैं कि "*" हमारे पास बह गया है - कोई अन्य प्रतीक। अगला, देखें कि क्या कोई कार्रवाई राज्य-सिग्नल जोड़ी के लिए परिभाषित की गई है। यदि परिभाषित किया गया है, निष्पादित करें। और अगले राज्य में आगे बढ़ें, अगर यह परिभाषित है (CURRENT चर को बदलें)। यदि परिभाषित नहीं किया गया है, तो वास्तव में यह हमारी मशीन के लिए एक घातक त्रुटि है।

शैक्षिक उद्देश्यों के लिए, निश्चित रूप से, हम मशीन को STDERR पर स्विच करने के बारे में जानकारी प्रदर्शित करते हैं, मुझे लगता है कि यदि आवश्यक हो, तो डिबग के लिए लॉग में इस आउटपुट को लपेटना आपके लिए मुश्किल नहीं होगा।

उदाहरण

आइए कुछ को लागू करने का प्रयास करें। इसे किसी तरह का चैटबॉट होने दें।
हम इसके आधार के रूप में निम्नलिखित नियमों का उपयोग करेंगे:

• कमांड निष्पादित करने से पहले आपको पहले अपना परिचय देना होगा ( लॉगिन )
• मेमोराइज़ कमांड पर, हम वह सब कुछ याद रखेंगे जो उपयोगकर्ता प्रवेश करता है, निकास कमांड पर समाप्त होता है
• कमांड एन पर, याद किए गए वाक्यांश संख्या एन को प्रदर्शित करें
• सत्र बाहर निकलने के आदेश द्वारा समाप्त किया जाएगा

तो, आइए इस उदाहरण के लिए एक रूपांतरण तालिका बनाएँ:

प्रतीक	राज्य	अगली अवस्था	प्रभाव
लॉगिन	INIT	सत्र	खुला सत्र
*	INIT	INIT	-
*	सत्र	सत्र	-
कहो	सत्र	सत्र	हम लाइन नंबर एन प्रिंट करते हैं
बाहर निकलें	सत्र	INIT	-
याद करना	सत्र	स्टोर	-
*	स्टोर	स्टोर	स्ट्रिंग को बफ़र में सहेजें
बाहर निकलें	स्टोर	सत्र	-

कुल में, मशीन की वर्णमाला में वर्ण (LOGIN, MEMORIZE, SAY, EXIT, *) होते हैं, मशीन में 3 राज्य होते हैं (INIT, SESSION और STORE)।

अच्छा, चलो इसे लागू करते हैं। सबसे पहले, हम कंस्ट्रक्टर में जंप टेबल सेट करेंगे, जहां आवश्यक हो - तथाकथित विधियों के लिंक जोड़ें। कोई कठिनाई नहीं :)

 package ChatBot; use FSM; @ISA = ("FSM"); use strict; use Carp; use vars qw($AUTOLOAD); sub new { my $proto = shift; my $class = ref($proto) || $proto; my $self = $class->SUPER::new("INIT"); $self->addState(STATE => "INIT", SYMBOL => "*", NEXT => "INIT", ACTION => \&doIntroduce); $self->addState(STATE => "INIT", SYMBOL => "LOGIN", NEXT => "SESSION", ACTION => \&doLogin); $self->addState(STATE => "INIT", SYMBOL => "EXIT", NEXT => "INIT", ACTION => \&doQuit); $self->addState(STATE => "SESSION", SYMBOL => "*", NEXT => "SESSION"); $self->addState(STATE => "SESSION", SYMBOL => "EXIT", NEXT => "INIT"); $self->addState(STATE => "SESSION", SYMBOL => "SAY", NEXT => "SESSION", ACTION => \&doSay); $self->addState(STATE => "SESSION", SYMBOL => "MEMORIZE",NEXT => "STORE"); $self->addState(STATE => "STORE", SYMBOL => "*", NEXT => "STORE", ACTION => \&doRemember); $self->addState(STATE => "STORE", SYMBOL => "EXIT", NEXT => "SESSION"); $self->{SESSION} = {}; $self->{LOGIN} = ""; return $self; } sub normalize { my ($self, $symbol) = @_; my $ret = {}; if ($symbol =~ /^(\S+)(.*)$/) { $ret->{SYMBOL} = uc $1; $ret->{DATA} = $2; $ret->{RAW} = $symbol; } else { $ret->{SYMBOL} = "*"; $ret->{DATA} = $symbol; $ret->{RAW} = $symbol; } return $ret; } sub doIntroduce { my $self = shift; print "Please introduce yourself first!\n"; return $self; } sub doLogin { my ($self, $symbol) = @_; print "Welcome," . $symbol->{DATA} . "\n"; $self->{LOGIN} = $symbol->{DATA}; $self->{SESSION}->{$self->{LOGIN}} = () unless exists $self->{SESSION}->{$self->{LOGIN}}; return $self; } sub doSay { my ($self, $symbol) = @_; if (defined $self->{SESSION}->{$self->{LOGIN}}->[$symbol->{DATA}]) { print $self->{SESSION}->{$self->{LOGIN}}->[$symbol->{DATA}]; } else { print "No record\n"; } return $self; } sub doRemember { my ($self, $symbol) = @_; push @{ $self->{SESSION}->{$self->{LOGIN}} }, $symbol->{RAW}; return $self; } sub doQuit { my ($self, $symbol) = @_; print "Bye bye!\n"; exit; return $self; } 1; 

संक्रमण आरेख इस प्रकार है।



इस मामले में परिवर्तन तालिका निम्न रूप में होगी:

 { 'INIT' => { '*' => { 'ACTION' => \&doIntroduce, 'NEXT' => 'INIT' }, 'LOGIN' => { 'ACTION' => \&doLogin, 'NEXT' => 'SESSION' }, 'EXIT' => { 'ACTION' => \&doQuit, 'NEXT' => 'INIT' } }, 'STORE' => { '*' => { 'ACTION' => \&doRemember, 'NEXT' => 'STORE' }, 'EXIT' => { 'NEXT' => 'SESSION' } }, 'SESSION' => { 'SAY' => { 'ACTION' => \&doSay, 'NEXT' => 'SESSION' }, '*' => { 'NEXT' => 'SESSION' }, 'MEMORIZE' => { 'NEXT' => 'STORE' }, 'EXIT' => { 'NEXT' => 'INIT' } } } 

आइए इन वर्गों का उपयोग करके सबसे सरल प्रोग्राम लिखें।

 use ChatBot; $bot = ChatBot->new(); while(<>) { $bot->process($_); } 

खैर, एक साधारण जाँच। इनपुट पर हम निम्नलिखित अनुक्रम देते हैं।

 hello world! login %username% hello world! say 3 memorize hey, do you really remember everything i would say? let's check exit say 0 exit hello login %username% say 1 exit 

हमें बाहर जाने के रास्ते पर क्या मिलता है?

 Please introduce yourself first! Welcome, %username% No record hey, do you really remember everything i would say? Please introduce yourself first! Welcome, %username% let's check 

सामान्य तौर पर, इसे स्वयं आज़माएं।

निष्कर्ष

इस प्रकार, हमने सबसे सरल परिमित राज्य मशीन को लागू किया। यह कुछ भी जटिल नहीं लगता है? यह कहां काम आ सकता है? खैर, चैट बॉट के साथ सब कुछ स्पष्ट है। उसी चीज़ के बारे में अगर दूसरी तरफ कोई व्यक्ति नहीं है, लेकिन लोहे का एक टुकड़ा है - आदेशों को प्रसारित करके और जवाब सुनकर हम एक बॉट लिख सकते हैं, उदाहरण के लिए, राउटर सेटिंग्स को घुमाकर। इंटरएक्टिव कमांड इंटरफेस? हां, हमने वास्तव में अब इसे लागू कर दिया है! एक स्टेटफुल प्रोटोकॉल का उपयोग कर एक सेवा से कनेक्ट करना चाहते हैं? कुछ भी आसान नहीं है!

मुझे उम्मीद है कि मेरा लेख किसी के लिए कम से कम उपयोगी था। हां, कार्यान्वयन आदिम है, बहुत सारे तैयार-तैयार लोग हैं। लेकिन खरोंच से कुछ करने की कोशिश करना दिलचस्प है, क्या यह नहीं है?

मुझे किसी भी टिप्पणी पर खुशी होगी।