🥨 🤙🏾 🎧 MySQL ट्यूरिंग मशीन एमुलेटर 🏢 🎳 📖

हाल ही में, एक साक्षात्कार में, मुझे केवल MySQL का उपयोग करके एक स्ट्रिंग को पार्स करने का कार्य दिया गया था।

उसके बाद, मैंने सोचा: सामान्य तौर पर, सिर्फ एक DBMS की मदद से इस तरह के जटिल कार्यों को कैसे हल किया जा सकता है? जवाब जल्दी मिल गया था: MySQL टूल्स का उपयोग करके, आप सामान्य रूप से किसी भी स्ट्रिंग मान्यता कार्य को हल कर सकते हैं। और इसे और अधिक सुविधाजनक और सार्वभौमिक तरीके से करने के लिए, यह एक आदिम परिमित राज्य मशीन एमुलेटर, या इससे भी बेहतर, ट्यूरिंग मशीन लिखने के लिए पर्याप्त है, केवल MySQL द्वारा प्रदान की गई केवल निर्माण का उपयोग करके। तो, चलिए प्रयोग शुरू करते हैं।

डिज़ाइन

कोई भी कार्यक्रम एक परियोजना से शुरू होता है। तो यह इस बार होगा। सबसे पहले, एक ट्यूरिंग मशीन क्या है, यह क्या करता है, यह क्या कर सकता है? वह जानती है, खुलकर, थोड़ा। इसके निपटान में एक अंतहीन बेल्ट और एक नियंत्रण उपकरण (गाड़ी), एक मशीन कर सकते हैं:

टेप के साथ बाएँ और दाएँ ले जाएँ
टेप प्रतीक से पढ़ें।
टेप सिंबल को लिखें
विभिन्न राज्यों में जाएं

रूसी में अनुवादित ट्यूरिंग मशीन के लिए निर्देश कुछ इस तरह है: "राज्य 1 में होने के नाते और प्रतीक" ए "पढ़कर, दाईं ओर जाएं और राज्य 2 पर जाएं"।

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

'>' - सही कदम

'<' - बाईं चाल

'#' - बंद करो

यहाँ मशीन के लिए निर्देशों का एक उदाहरण दिया गया है:

0,1,>, 1

1,0,>, 2

2.0,>, 3

3 ,,>, 4

4 ,, 1, 4

4,1, #, 4

यदि टेप पर लिखा गया बाइनरी नंबर 4 है, और यदि ऐसा है, तो यह बहुत बेकार प्रोग्राम की जाँच करता है, यह एक स्थान के माध्यम से नंबर 1 लिखता है।

यह मशीन कुछ मान्यताओं का अर्थ लगाती है।

सबसे पहले, नियंत्रण डिवाइस की प्रारंभिक स्थिति अच्छी तरह से बाईं ओर हो सकती है, और मूल डेटा के दाईं ओर नहीं।

दूसरे, टेप केवल एक दिशा में "अनंत" है।

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

संपूर्ण परियोजना में निम्नलिखित भाग शामिल होंगे:

एक एकल क्षेत्र से मिलकर एक टेप का अनुकरण करने के लिए डिज़ाइन की गई तालिका
त्रुटि उत्पादन तालिका, एक क्षेत्र के साथ भी
निर्देशों के लिए एक तालिका, 4 क्षेत्रों (प्रारंभिक स्थिति, प्रतीक को पढ़ने, कार्रवाई, परिणामी अवस्था) से।
एक संग्रहीत पुनरावर्ती प्रक्रिया जिसमें एम्यूलेटर लॉजिक होता है।

त्रुटि आउटपुट तालिका किसके लिए है? खैर, यह अभी भी कुछ प्रकार का है, लेकिन सबसे आदिम भाषा का एक व्याख्याकार है। इसलिए, क्यों ठोकर खाई कार्यक्रम की जानकारी शानदार नहीं होगी।

तो, एमुलेटर कैसे काम करेगा? आप नियम एक निर्देश - एक पंक्ति के अनुसार, इसके लिए इच्छित तालिका में कार्यक्रम का पाठ डालें, टेप तालिका में स्रोत डेटा डालें और प्रक्रिया शुरू करें। आप अपने कार्यक्रम में जो लिखते हैं, उसके आधार पर यह टेप पर समाप्त हो जाएगा। और अगर कुछ पूरी तरह से अप्रत्याशित है, तो आप त्रुटि तालिका को देख सकते हैं।

खैर, यह कोडिंग भाग शुरू करने का समय है।

हम विकास कर रहे हैं

सबसे पहले, एक डेटाबेस और टेबल बनाएं।

CREATE DATABASE turing; CREATE TABLE program ( in_state INT NOT NULL , sread VARCHAR( 1 ) NOT NULL , actions VARCHAR( 1 ) NOT NULL , out_state INT NOT NULL ) ENGINE = MYISAM CHARACTER SET utf8 COLLATE utf8_unicode_ci; CREATE TABLE output_string ( output TEXT NOT NULL ) ENGINE = MYISAM ; CREATE TABLE ribbon ( sinput TEXT NOT NULL ) ENGINE = MYISAM ;

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

अब हम सबसे महत्वपूर्ण बात पर आगे बढ़ते हैं - प्रक्रिया का निर्माण। लेकिन इससे पहले, आपको MySQL config में पुनरावर्तन को सक्षम करने की आवश्यकता है, क्योंकि हमें इसकी बहुत आवश्यकता है।

ऐसा करने के लिए, my.cnf में max_sp_recursion_depth = 255 लिखें।

सबसे पहले, मैं पूरी तरह से प्रक्रिया कोड दूंगा, और नीचे मैं एक डिक्रिप्शन दूंगा, ताकि टिप्पणियों के साथ दृश्य को खराब न करें।

 delimiter // CREATE procedure turing(IN sstate INT(11), IN pos INT(11)) BEGIN turing:BEGIN SET @p=pos; SET @sstate=sstate; SELECT @inread:=SUBSTRING(sinput, @p, 1) FROM ribbon; SELECT @instate:=in_state, @sread:=sread, @actions:=actions, @out_state:=out_state, @numrows:=count(in_state) FROM program WHERE in_state = @sstate AND sread = @inread; IF @numrows > 1 THEN UPDATE output_string SET output= 'Confused :('; LEAVE turing; ELSEIF @numrows = 0 THEN UPDATE output_string SET output='Do not understand what to do next :('; LEAVE turing; ELSE SELECT @lin:= LENGTH(sinput) FROM ribbon; SELECT @input:=sinput FROM ribbon; IF @actions = '>' THEN IF @lin = pos THEN SELECT @new_input:=CONCAT(sinput, ' ') FROM ribbon; UPDATE ribbon SET sinput=@new_input; END IF; SET @pos=pos+1; ELSEIF @actions = '<' THEN IF pos>1 THEN SET @pos=pos-1; ELSE UPDATE output_string SET output='Carriage has left the ribbon'; LEAVE turing; END IF; ELSEIF @actions = '#' THEN LEAVE turing; ELSE SELECT @head:=SUBSTRING(sinput, 1, pos-1) FROM ribbon; SELECT @tail:=SUBSTRING(sinput, pos+1, @lin) FROM ribbon; SELECT @inp:=CONCAT(@head, @actions, @tail); UPDATE ribbon SET sinput=@inp; SET @pos=pos; END IF; CALL turing(@out_state, @pos); END IF; END; END //

शुरुआत स्पष्ट है, हम एक प्रक्रिया बनाते हैं और इसके लिए दो पैरामीटर पास करते हैं - राज्य मशीन की स्थिति और नियंत्रण डिवाइस की स्थिति।

अगला, हम अपने BEGIN ... END को ट्यूरिंग लेबल के साथ चिह्नित करते हैं ताकि आप इसे बाहर निकलने के लिए उपयोग कर सकें।

उसके बाद, हमने @inread वैरिएबल में पढ़ा, जिस पर गाड़ी वर्तमान में स्थित है।

हम प्रोग्राम टेबल से उन पंक्तियों का चयन करते हैं जिनमें राज्य पारित पैरामीटर के बराबर है, और सॉर्ट फ़ील्ड - जिस चरित्र को पढ़ा जाना है वह वास्तविक चरित्र के बराबर है जिस पर हमारा नियंत्रण उपकरण स्थित है। ये दो पैरामीटर विशिष्ट रूप से ट्यूरिंग मशीन के लिए निर्देश निर्धारित करते हैं, इसलिए, शर्त को पूरा करने वाली एक पंक्ति अद्वितीय होनी चाहिए।

हम एक ऐसी स्थिति को संभालते हैं जहां कोई संगत निर्देश नहीं हैं - एमुलेटर अपना काम एक त्रुटि के साथ समाप्त करता है - वह सिर्फ यह नहीं जानता कि आगे क्या करना है।

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

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

बाईं ओर एक आंदोलन के मामले में, हम उस स्थिति को संभालते हैं जब गाड़ी टेप की सीमाओं से परे जाती है। कुछ होना नहीं है। क्षमा करें, टेप केवल एक दिशा में "अंतहीन" है।

जब प्रोग्राम एक "स्टॉप" सिग्नल भेजता है, तो # प्रतीक द्वारा इंगित किया जाता है, हम प्रक्रिया से बाहर निकलते हैं।

यदि प्रतीक उपरोक्त में से किसी से मेल नहीं खाता है, अर्थात, यह नहीं है>, <या #, इसका मतलब यह है कि इसे टेप पर लिखा जाना चाहिए, वर्तमान को अधिलेखित करना। हम इस ट्रिक को साधारण बिल्ट-इन फंक्शन CONCAT () का उपयोग करके करते हैं।

इसके अलावा, हम उसी भावना को जारी रखते हैं, पहले से ही संशोधित पैरामीटर मानों को पार करते हैं। इस मामले में @out_state आउटपुट स्थिति है, जो अगले निर्देश के लिए इनपुट है।

परीक्षण

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

कार्यक्रम काफी सरल रूप से काम करेगा - एक इनपुट के रूप में पात्रों की एक स्ट्रिंग को स्वीकार करने के लिए और, यदि यह स्ट्रिंग एक सही रोमन संख्या है, तो स्पेस बार "ओके" के माध्यम से एक स्थान प्रिंट करें।

स्पष्ट जटिलता के बावजूद, कार्य सरल है। यह निर्धारित करने के लिए रोमन नंबर लिखने के लिए उपयोग किए जाने वाले प्रत्येक वर्ण के लिए आवश्यक है जो इसका पालन नहीं कर सकता है। उदाहरण के लिए, L का अनुसरण C नहीं किया जा सकता है, अर्थात प्रवेश LC को रोमन संख्या नहीं माना जा सकता है। संख्या 50 को केवल एल। या के रूप में लिखा गया है, उदाहरण के लिए, लगातार I की अधिकतम संख्या 3 है, इसलिए IIII एक रोमन संख्या नहीं है, आदि। मैं इन नियमों पर विस्तार से ध्यान नहीं दूंगा, क्योंकि यह एक अलग लेख का विषय है।

हमारे इनपुट वर्णमाला में निम्नलिखित वर्ण हैं: M, D, C, L, X, V, और I। मैंने प्रारंभिक राज्य संख्या 47 को कॉल करने का निर्णय लिया है, क्योंकि मुझे 47 नंबर पसंद है, और यह भी प्रदर्शित करने के लिए कि आप किसी भी राज्य का उपयोग कर सकते हैं , और यह 0 से शुरू करने के लिए आवश्यक नहीं है (कम से कम इस एमुलेटर में, शून्य स्थिति बिल्कुल भी आवश्यक नहीं है)।

डेटाबेस में हमारे कार्यक्रम डालें:

कार्यक्रम मूल्यों में सम्मिलित करें

(47, '', '#', 47), (48, '', '>', 64), (49, '', '>', 64)

(50, '', '>', 64), (51, '', '>', 64), (52, '', '>', 64)

(53, '', '>', 64), (54, '', '>', 64), (55, '', '>', 64)

(56, '', '>', 64), (57, '', '>', 64), (58, '', '>', 64)

(59, '', '>', 64), (60, '', '>', 64), (61, '', '>', 64)

(62, '', '>', 64), (63, '', '>', 64), (65, '', '>', 64)

(66, '', '>', 64), (64, '', 'ओ', 64), (64, 'ओ', '>', 70),

(70, '', 'के', 70), (70, 'के', '>', 71),

(47, 'मैं', '>', 48), (48, 'वी', '>', 51), (48, 'X', '>', 51),

(51, 'वी', '#', 51), (51, 'सी', '#', 51), (51, 'एल', '#', 51),

(51, 'डी', '#', 51), (51, 'एम', '#', 51), (51, 'एक्स', '#', 51),

(48, 'C', '#', 48), (48, 'L', '#', 48), (48, 'D', '#', 48),

(48, 'M', '#', 48), (48, 'I', '>', 49), (49, 'I', '>', 50),

(50, 'मैं', '#', 50), (50, 'वी', '#', 50), (50, 'सी', '#', 50),

(50, 'एल', '#', 50), (50, 'डी', '#', 50), (50, 'एम', '#', 50),

(50, 'एक्स', '#', 50),

(47, 'वी', '>', 52), (52, 'आई', '>', 48), (52, 'वी', '#', 48),

(52, 'X', '#', 48), (52, 'C', '#', 48), (52, 'M', '#', 48),

(52, 'डी', '#', 48), (52, 'एल', '#', 48), (47, 'एक्स', '>', 53),

(53, 'V', '>', 52), (53, 'I', '>', 48), (53, 'D', '#', 53),

(53, 'एम', '#', 53), (53, 'एल', '>', 53), (53, 'सी', '>', 53),

(53, 'X', '>', 55), (55, 'D', '#', 55), (55, 'M', '#', 55)

(55, 'सी', '#', 55), (55, 'एल', '#', 55), (55, 'वी', '>', 52),

(55, 'I', '>', 48), (55, 'X', '>', 56), (56, 'X', '#', 56),

(56, 'डी', '#', 56), (61, 'सी', '>', 62), (56, 'एम', '#', 56),

(56, 'सी', '#', 56), (56, 'एल', '#', 56), (56, 'वी', '>', 52),

(56, 'मैं', '>', 48),

(47, 'L', '>', 54), (54, 'X', '>', 53), (54, 'V', '>', 52),

(54, 'मैं', '>', 48), (54, 'डी', '#', 54), (54, 'सी', '#', 54),

(54, 'एम', '#', 54), (54, 'एल', '#', 54),

(47, 'C', '>', 59), (59, 'X', '>', 53), (59, 'I', '>', 48),

(59, 'एल', '>', 54), (59, 'वी', '>', 52), (59, 'एम', '>', 65),

(65, 'एम', '#', 65), (65, 'वी', '>', 59), (65, 'एक्स', '>', 59),

(65, 'मैं', '>', 59), (65, 'एल', '>', 59), (65, 'सी', '#', 65),

(59, 'डी', '>', 66), (66, 'डी', '#', 66), (66, 'एम', '#', 65)

(66, 'V', '>', 59), (66, 'X', '>', 59), (66, 'I', '>', 59),

(66, 'L', '>', 59), (66, 'C', '#', 65), (59, 'C', '>', 61)

(61, 'C', '>', 62), (61, 'I', '>', 47), (62, 'X', '>', 53),

(62, 'मैं', '>', 48), (62, 'एल', '>', 54), (62, 'वी', '>', 52),

(62, 'सी', '#', 62), (61, 'एम', '#', 59), (61, 'डी', '#', 59),

(62, 'एम', '#', 62), (62, 'डी', '#', 62),

(47, 'डी', '>', 60), (60, 'एम', '#', 60), (60, 'सी', '>', 59),

(60, 'डी', '#', 60), (60, 'एक्स', '>', 53), (60, 'आई', '>', 48),

(60, 'एल', '>', 54), (60, 'वी', '>', 52),

(47, 'एम', '>', 63), (63, 'एम', '>', 63), (63, 'सी', '>', 59),

(63, 'डी', '>', 60), (63, 'एक्स', '>', 53), (63, 'आई', '>', 48),

(63, 'वी', '>', 52), (63, 'एल', '>', 54)

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

निम्नलिखित ब्लॉक मशीन की स्थितियों और इनपुट वर्णमाला के अक्षरों के विभिन्न संयोजनों से निर्देश हैं। कोड के अधिकांश टुकड़ों का उपयोग कई बार किया जाता है। उदाहरण के लिए, जब हमने प्रतीक I के लिए सभी नियम लिखे, और प्रतीक V के लिए लिखें, तो हम लिख सकते हैं (47, 'V', '>', 52), (52, 'I', '>', 48), जहां राज्य 48 पहले ही हमारे द्वारा पहले ही वर्णित किया जा चुका है।

और परिणाम क्या है? CCCXXIV (सही संख्या) कहते हुए, इनपुट लाइन के रूप में डालें। अब हम कंसोल में टाइप करते हैं:

mysql> कॉल ट्यूरिंग (47,1) //

47 - प्रारंभिक अवस्था, 1 - नियंत्रण डिवाइस की स्थिति।

हमें मिलता है:

+ -------------------------------------- +

| CCCXXIV ओके |

+ -------------------------------------- +

अब गलत संख्या का प्रयास करें, MXXLC कहते हैं।

हमें मिलता है:

+ ---------------- +

| MXXLC |

+ ---------------- +

वह सब है!

संक्षेप में देना

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

बहुत सारे पागल विचारों और अच्छी प्रोग्रामिंग प्राप्त करें!

MySQL ट्यूरिंग मशीन एमुलेटर

डिज़ाइन

हम विकास कर रहे हैं

परीक्षण

संक्षेप में देना

More articles: