मछली कौन पैदा करता है? या नियमित भाषा में आइंस्टीन की पहेली को हल करना

पाँच रंगीन घरों के बारे में पहेली का सामना करना पड़ा, जिनमें से प्रत्येक में एक व्यक्ति अपने प्यारे जानवरों, एक पेय और सिगरेट के साथ रहता है। इस रहस्य को आइंस्टीन के लिए जिम्मेदार ठहराया जाता है, हालांकि इसके लिए कोई प्रत्यक्ष प्रमाण नहीं है। इस पहेली का पूरा पाठ विकिपीडिया पर है ।



यह कागज पर या मन में हल किया जा सकता है, क्रमिक रूप से अनुचित विकल्पों को समाप्त कर सकता है। हालाँकि, इसे तकनीकी रूप से भी हल किया जा सकता है। एक तरीका यह है कि एक प्रस्तावना कार्यक्रम लिखा जाए। लेकिन यहां मैं इसे सरल तंत्र - नियमित अभिव्यक्तियों का उपयोग करके हल करना चाहता हूं। अर्थात्, पहेली की स्थितियों को regexp भाषा में अनुवादित करें और स्ट्रिंग्स के पूरे मान्य सेट में उपयुक्त स्ट्रिंग को खोजने के लिए कार्य को कम करें। वैसे, लाइनों का यह सेट आंकड़ा में दिखाया गया है।

विचार

यह विचार मेरा नहीं है, मैंने इसे एक वीडियो व्याख्यान में सुना। हालाँकि, वहाँ उन्होंने इसे बहुत परिष्कृत रूप से हल किया। मैंने इसे और अधिक सरलता से और स्पष्ट रूप से हल करने की कोशिश की।

सुविधा के लिए, यहाँ पहेली का पाठ है:

1. नॉर्वेजियन पहले घर में रहता है।
2. अंग्रेज लाल घर में रहता है।
3. ग्रीन हाउस सफेद के बाईं ओर स्थित है, उसके बगल में।
4. डेन चाय पी रहा है
5. जो लोग मार्लबोरो धूम्रपान करते हैं वे बिल्लियों के प्रजनन के लिए रहते हैं।
6. जो पीले घर में रहता है वह डनहिल को पीटता है।
7. जर्मन रोथ्मेन को धूम्रपान करता है।
8. जो केंद्र में रहता है वह दूध पीता है।
9. जो मार्लबोरो धूम्रपान करता है उसका पड़ोसी पानी पीता है।
10. पाल मॉल का धूम्रपान करने वाले पक्षी बढ़ते हैं।
11. स्वेड कुत्तों को पाल रहा है।
12. एक नॉर्वेजियन ब्लू हाउस के बगल में रहता है।
13. वह जो घोड़ों को एक नीले घर में रहता है।
14. जो भी विनफील्ड को धूम्रपान करता है वह बीयर पीता है।
15. ग्रीन हाउस में उन्होंने कॉफी पी।

प्रश्न: कौन मछली प्रजनन करता है?

समस्या को हल करने के लिए, आपको घरों, फूलों, राष्ट्रीयताओं, पेय और सिगरेट का एक क्रम ढूंढना होगा ताकि वे ऊपर दिए गए नियमों को पूरा कर सकें

और इसलिए हम क्या और कहाँ देखेंगे। पहले आपको किसी तरह से नियमों को औपचारिक रूप देने की आवश्यकता है। हमारे पास पाँच घर, फूल, राष्ट्रीयताएँ, पेय, जानवर और सिगरेट हैं। "निवासियों" के साथ एक घर का एक मनमाना संस्करण इस तरह दिख सकता है:

german white cat beer malboro 

लेकिन यह पर्याप्त नहीं है, क्योंकि हमारे पास नियम हैं जो घरों और वस्तुओं की पारस्परिक व्यवस्था को ध्यान में रखते हैं (उदाहरण के लिए, नियम: 1, 3, 5 ...)। हम श्रृंखला में पांच घरों को एक पंक्ति में रखकर इसे ध्यान में रखेंगे:

 german white cat beer malboro englishman red dog water pallmall norwegian green fish milk winfield dane blue bird tea dunhill swede horse yellow coffee rothmans 

आइटम रखने के लिए विकल्पों में से एक ऊपर की पंक्ति है। इस मामले में, गलत है। यदि हम सभी संभावित विकल्पों की रचना करते हैं, और इसे एक पाठ में रखते हैं, तो हमें निम्नलिखित मिलते हैं:

 ncadsncadsncadsncadsn cads ncadsncadsncadsncadsn cads ncadsncadsncadsncadsn cads ... 

जहाँ n - राष्ट्र, c - रंग, a - जानवर, d - पेय, s - सिगरेट। और इनमें से प्रत्येक अक्षर इसके पाँच अर्थों में से एक ले सकता है।

अद्भुत। नियमों को नियमित अभिव्यक्ति भाषा में अनुवाद करने के लिए क्या करना है:

1. ^ प्रेमिका \ w +
2. \ w + englishman लाल \ w +
3. \ w + डेन \ w \ w चाय \ w +
4. ...

और अगर रेखा सभी नियमों को मानती है, तो हमें एक समाधान मिला! यह केवल मछली के साथ घर में राष्ट्रीयता को देखने के लिए बनी हुई है। यह खोज का मुख्य विचार है: एक पाठ का निर्माण करना और नियमित अभिव्यक्तियों के साथ उस पर चलना।

लेकिन कुछ बुरी खबर है। जो पाठ खोजा जाएगा वह बहुत बड़ा हो सकता है। अधिक सटीक रूप से, यह (5!) ^ 5 लाइनों (~ 24 बिलियन) का आकार होगा। यह केवल जाँच करने के लिए नहीं है, इसे उत्पन्न करना भी मुश्किल होगा। लेकिन अच्छी खबर है। हम इस सभी पाठ को उत्पन्न नहीं कर सकते हैं, लेकिन नियमित अभिव्यक्तियों को जोड़ने के संचालन का उपयोग कर सकते हैं। यही है, हम नियमित अभिव्यक्ति * (सभी संभव रेखाएं) की सभी सामान्य रेखाएं, उन पंक्तियों के साथ पाते हैं जो समस्या के नियमों के नियमित अभिव्यक्ति देते हैं । चौराहे के बाद बनी रहने वाली वह लाइन (और शायद लाइनें) समस्या का समाधान होगी।

दुर्भाग्य से, मुझे ऐसे इंजन नहीं पता हैं जो नियमित अभिव्यक्ति को पार कर सकें। इसलिए, आपको सीधे परिमित राज्य मशीनों का उपयोग करना होगा जो किसी भी regexp से गुजरती हैं।

कार्यान्वयन

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

चरण 1 - बेसिक ऑटोमेटा का निर्माण

सभी ऑब्जेक्ट की सूची के साथ एक टेक्स्ट फ़ाइल बनाएं। यह हमारी वर्णमाला होगी।

 norwegian englishman dane german swede white red ... 

हम बुनियादी ऑटोमेटा का निर्माण करते हैं, जिनमें से प्रत्येक वर्णमाला के केवल एक शब्द को स्वीकार करता है।

 j=1 for i in `cat alph`; do echo -e "0 1 $j\n1" | fstcompile --acceptor > $i ((j=$j+1)) done 

fstcompile एक ओपनफैस्ट पैकेज कमांड है जो ऑटोमेटन के एक टेक्स्ट प्रतिनिधित्व को बाइनरी में संकलित करता है। इस मशीन में बाद में विभिन्न कार्यों को लागू करने के लिए यह आवश्यक है।

और इसलिए, हमारे पास स्वचालित फ़ाइलों की एक सूची है। वे बहुत तुच्छ हैं। उदाहरण के लिए, एक बीयर मशीन इस तरह दिखाई देगी:



यह नियमित अभिव्यक्ति "बीयर" के बराबर है। अब तक, सब कुछ काफी सरल है। इसके अलावा, हमें दो और बुनियादी ऑटोमेटा की आवश्यकता होगी - एक खाली सेट, और किसी भी स्ट्रिंग, अर्थात्। तारांकन *। हम निर्माण कर रहे हैं।

चरण 2 - एक खाली मशीन और एक तारांकन बनाएँ

खाली लाइन, स्वचालित 'खाली':

  echo '0' | fstcompile --acceptor > empty 

स्प्रोकेट, स्वचालित 'स्टार':

 cp empty star for i in `cat alph`; do fstunion star $i star done fstclosure star star 

उत्तरार्द्ध बुनियादी ऑटोमेटा और क्लोजर के एक साधारण संघ द्वारा किया जाता है। नियमित अभिव्यक्तियों में, यह सिर्फ (अंग्रेजी में है | dane | ... | | बिल्ली | कुत्ता | ...) *। यह मशीन इस तरह होगी:

चरण 3 - घरों का निर्माण

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

 c="./concat.sh" $c norwegian star > r1 $c star englishman red star > r2 $c star animal drink cigarette nation star > r3 $c star dane color animal tea star > r4 $c star malboro nation color cat star > r5_0 $c star cat drink cigarette nation color animal drink malboro star > r5_1 $c star yellow animal drink dunhill star > r6 $c star german color animal drink rothmans > r7 $c house house nation color animal milk cigarette house house > r8 $c star malboro nation color animal water star > r9_0 $c star water cigarette nation color animal drink malboro star > r9_1 $c star bird drink pallmall star > r10 $c star swede color dog star > r11 $c star norwegian color animal drink cigarette nation blue star > r12_0 $c star blue animal drink cigarette norwegian star > r12_1 $c star blue horse star > r13 $c star beer winfield star > r14 $c star green animal coffee star > r15 fstunion r5_0 r5_1 > r5 fstunion r9_0 r9_1 > r9 fstunion r12_0 r12_1 > r12 

नियम 5, 9 और 12 समग्र हैं। मैं प्रत्येक भाग को अलग-अलग परिभाषित करता हूं, और फिर संघ करता हूं। Concat.sh स्क्रिप्ट बस तर्क में पारित मशीनों का संघटन करती है:

 cp empty _c for i in $*; do fstconcat _c $i _c done; cat _c; rm _c; 

इसलिए, आउटपुट पर हमें ऑटोमेटा आर 1, आर 2 ..., आर 15 मिलता है। सब कुछ अंतिम चरण के लिए तैयार है।

एक कदम - अंतर

 ./intersect.sh r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15 > result 

जहां intersect.sh तर्कों में ऑटोमेटा का प्रतिच्छेदन है।

 cp cl _c for i in $*; do fstintersect _c $i _c done; cat _c; rm _c; 

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

 i="./intersect.sh" d="fstdifference" for i in `cat alph`; do fstdifference cl $i > differ fstconcat differ $i | fstconcat - differ | fstrmepsilon - | fstdeterminize - | fstminimize - > ${i}_cont done cp result out for i in `ls *_cont`; do echo $i fstintersect $i out | fstrmepsilon - | fstdeterminize - | fstminimize - out done rm differ rm *_cont 

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



यह मशीन की एक आंशिक छवि है (सब कुछ फिट नहीं हुआ)। हर पाँच शब्द एक घर को परिभाषित करते हैं। जैसा कि आंकड़े से देखा जा सकता है, जर्मन नस्ल की मछली।

निष्कर्ष

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

पी एस और हाँ, mse वास्तव में विकृतियों के बारे में बहुत कुछ जानता है :)