दो नियमित भाषाओं का परीक्षण चौराहे

Question

मैं यह जांचना चाहता हूं कि दो भाषाओं में एक स्ट्रिंग सामान्य है या नहीं। ये दोनों भाषाएं नीचे वर्णित नियमित भाषाओं के उप-समूह से हैं और मुझे केवल यह जानने की आवश्यकता है कि दोनों भाषाओं में एक स्ट्रिंग मौजूद है या नहीं, उदाहरण स्ट्रिंग का उत्पादन न करें।

भाषा

/foo/**/bar/*.baz

जहां ** मैचों 0 या अधिक वर्ण, और * मैचों शून्य या अधिक अक्षर हैं जो / नहीं हैं, और सभी की तरह एक ग्लोब की तरह स्ट्रिंग द्वारा निर्दिष्ट किया जाता अन्य पात्र शाब्दिक हैं।

कोई भी विचार?

धन्यवाद, माइक

संपादित करें:

मैं कुछ जो अच्छा प्रदर्शन करने लगता है लागू किया, लेकिन अभी तक एक शुद्धता सबूत की कोशिश करने के लिए है। आप दोनों भाषाओं के लिए source और unit tests

Answer 1

बिल्ड एफएएस A और B देखते हैं, और "चौराहे एफए" AnB निर्माण कर सकते हैं। यदि AnB में प्रारंभिक स्थिति से कम से कम एक स्वीकार्य राज्य पहुंच योग्य है, तो एक शब्द है जो दोनों भाषाओं में है।

AnB का निर्माण मुश्किल हो सकता है, लेकिन मुझे यकीन है कि एफए पाठ्यपुस्तकें हैं जो इसे कवर करती हैं। दृष्टिकोण मैं ले जाएगा है:

• AnB के राज्यों में क्रमश: A और B के राज्यों की कार्तीय उत्पाद है। AnB में एक राज्य (a, b) लिखा गया है जहां aA और b में एक राज्य B में एक राज्य है।
• एक संक्रमण (a, b) ->r (c, d) (अर्थ, वहाँ प्रतीक r पर (c, d) करने के लिए (a, b) से एक संक्रमण है) मौजूद है iff a ->r cA में एक संक्रमण है, और b ->r dB में एक संक्रमण है।
• (a, b) iff a और b क्रमशः A और B में राज्यों शुरू कर रहे हैं AnB में एक शुरुआत के राज्य है।
• (a, b)AnB में एक स्वीकार्य स्थिति है यदि प्रत्येक अपने संबंधित एफए में एक स्वीकार्य राज्य है।

यह सब मेरे सिर के ऊपर से है, और इसलिए पूरी तरह से अप्रमाणित है!

Answer 2

मैंने अभी एक त्वरित खोज की है और यह समस्या निर्णायक है (उर्फ किया जा सकता है), लेकिन मुझे ऐसा करने के लिए किसी भी अच्छे एल्गोरिदम के बारे में पता नहीं है। एक है समाधान है:

1. Convert दोनों नियमित NFAs एक को भाव और बी
2. एक NFA, सी, कि ए और बी के चौराहे का प्रतिनिधित्व करता है बनाएं
3. अब 0 से प्रत्येक स्ट्रिंग को सी में राज्यों की संख्या से आजमाएं और देखें कि सी इसे स्वीकार करता है (यदि स्ट्रिंग लंबा है तो इसे एक बिंदु पर राज्यों को दोहराना चाहिए)।

मुझे पता है कि यह पालन करना थोड़ा मुश्किल हो सकता है लेकिन यह एकमात्र तरीका है जिसे मैं जानता हूं।