5
को देखते हुए दो गैर नियतात्मक परिमित ऑटोमेटा एम 1 और M2, यह तय करने के लिए कि क्या एम 1 द्वारा स्वीकार किए जाते भाषा M2 द्वारा स्वीकार किए जाते भाषा का सुपरसेट है एक कुशल एल्गोरिथ्म है?क्या यह तय करने के लिए एक कुशल एल्गोरिदम है कि एक एनएफए द्वारा स्वीकार की जाने वाली भाषा किसी अन्य द्वारा स्वीकार की जाने वाली भाषा का सुपरसेट है या नहीं?
मुझे आश्चर्य है, क्या आप एनएफए आइसोमोर्फिज्म को किसी अन्य एनपी पूर्ण समस्या से कमी के बारे में जानते हैं? – hugomg
@ मिसिनो: मैंने एक पेपर को एक लिंक जोड़ा जो कम से कम सावधानी से व्याख्या करता है। – Mikola
मिकोला, आपका उत्तर सही है लेकिन आपका शब्द गलत है: आइसोमोर्फिक का अर्थ "बराबर आकार" है, दो automatas isomorphic iff हैं, उनके राज्यों के बीच 1-1 मैपिंग है, जैसे ब्लै ब्ला। जो यहां प्रासंगिक नहीं है, दो automatas एक ही भाषा को आइसोमोर्फिक के बिना स्वीकार कर सकते हैं। (यह भ्रम में जोड़ता है कि ग्राफ़ आइसोमोर्फिज्म भी एनपी-हार्ड है) यदि आप अपना जवाब "चाहे दो एनएफए एक ही भाषा स्वीकार करते हैं" के बजाय संपादित करते हैं, "क्या दो एनएफए आइसोमोर्फिक थे" सभी ठीक होंगे। –