कि क्या यह भाषा डिसाइडेबल और पहचानने योग्य है

Question

L1 और L2 भाषाएं हैं अगर हम एक नई भाषा

INTERLACE(L1, L2) = {w1v1w2v2 . . . wnvn | w1w2 . . . wn ∈ L1, v1v2 . . . vn ∈ L2}. 

उदाहरण के लिए है, अगर abc ∈ L1 और 123 ∈ L2, तो a1b2c3 ∈ INTERLACE(L1, L2)

मुझे लगता है कि INTERLACE कैसे साबित कर सकते हैं है:

1. डिसाइडेबल?
2. पहचानने योग्य?

मैं दिखाने के लिए कि कैसे इस भाषा नियमित है। डिसाइडेबल के लिए मैं इतना यकीन नहीं कर रहा हूँ ..

यहाँ मैं क्या सोचता:

दिखाने के लिए कि डिसाइडेबल भाषाओं के वर्ग संचालन INTERLACE के तहत बंद कर दिया है पता चलता है कि अगर ए और बी दो डिसाइडेबल भाषाएं हैं की जरूरत है , तो INTERLACE भाषा को खोजने योग्य तरीका खोजने का तरीका है। A, B डिसाइडेबल भाषाओं और M1, M2 दो TM जो निर्णय लेते हैं, क्रमशः मान लीजिए।

मुझे लगता है कि मुझे कहना है कि भाषा को पहचानने वाले डीएफए का निर्माण कैसे करना है?

Answer 1

L1 और L2decidable ==>INTERLACE(L1, L2) डिसाइडेबल

Wikipedia से प्रशस्ति पत्र:

एक पुनरावर्ती (भी डिसाइडेबल) भाषा की अवधारणा के लिए दो बराबर प्रमुख परिभाषाएँ हैं:
। ..
2. एक पुनरावर्ती भाषा एक औपचारिक भाषा है जिसके लिए एक ट्यूरिंग मशीन है कि, जब प्रस्तुत वहां मौजूद है किसी भी सीमित इनपुट स्ट्रिंग के साथ, स्ट्रिंग भाषा में है, और रोकता है और स्वीकार करता है, और अन्यथा रोकता है और अस्वीकार करता है।

इस परिभाषा का उपयोग करना:

• तो L1 और L2, डिसाइडेबल हैं तो एल्गोरिदम (या ट्यूरिंग मशीन) M1 और M2 मौजूद हैं, ताकि:

  • M1 सभी आदानों स्वीकार करता w ∈ L1 और सभी इनपुट w ∉ L1 को अस्वीकार करता है।
  • M2 सभी आदानों v ∈ L2 स्वीकार करता है और सभी आदानों v ∉ L2 को खारिज कर दिया।

• अब एल्गोरिथ्म M जो सभी आदानों x ∈ INTERLACE(L1, L2) स्वीकार करता है और सभी आदानों x ∉ INTERLACE(L1, L2) को खारिज कर दिया निर्माण, इस प्रकार है:

  • एक इनपुट x1 x2 .. xn को देखते हुए। इनपुट x1 x3 x5 .. xn-1 के लिए
  • भागो M1:
  • तो n अजीब है, इनपुट अस्वीकार अन्यथा (n भी है)। M1 इस इनपुट को खारिज कर दिया है, तो M अपने इनपुट और खत्म को खारिज कर दिया है, अन्यथा (M1 अपने इनपुट स्वीकार किए जाते हैं):
  • भागो इनपुट x2 x4 x6 .. xn के लिए M2। यदि M2 इस इनपुट को अस्वीकार करता है, तो M अपने इनपुट को अस्वीकार करता है, अन्यथा M इसके इनपुट को स्वीकार करता है।

एक आसानी से साबित कर सकते हैं कि MINTERLACE(L1, L2) के लिए निर्णय एल्गोरिथ्म है, इस प्रकार, भाषा डिसाइडेबल है।

L1 और L2recognizable ==>INTERLACE(L1, L2) पहचानने

Wikipedia से प्रशस्ति पत्र:
...
:

एक रिकर्सिवली इन्युमरेबल (भी पहचानने) भाषा के तीन बराबर परिभाषाएँ हैं 3. एक पुनरावर्ती संख्यात्मक भाषा एक औपचारिक भाषा है जिसके लिए एक ट्यूरिंग मशीन मौजूद है (या अन्य कम्प्यूटेबल फ़ंक्शन) जो भाषा में किसी भी स्ट्रिंग के साथ इनपुट के रूप में प्रस्तुत किए जाने पर रोक देगा और स्वीकार करेगा लेकिन भाषा में नहीं होने वाली स्ट्रिंग के साथ प्रस्तुत होने पर या तो हमेशा रोक और अस्वीकार कर सकता है। इसे पुनरावर्ती भाषाओं में तुलना करें, जिसके लिए ट्यूरिंग मशीन सभी मामलों में रुकती है।

सबूत 'decidable' संपत्ति के सबूत के समान ही है।

• तो L1 और L2, पहचानने योग्य होते हैं तो एल्गोरिदम R1 और R2 मौजूद हैं, कि इतने:

  • R1 सभी आदानों w ∈ L1 स्वीकार करता है और को खारिज कर दिया या सभी आदानों w ∉ L1 के लिए हमेशा के लिए लूप।
  • R2 सभी इनपुट v ∈ L2 स्वीकार करता है और सभी इनपुट के लिए या को हमेशा अस्वीकार करता है।

• एल्गोरिथ्म R जो सभी आदानों x ∈ INTERLACE(L1, L2) स्वीकार करता है और को खारिज कर दिया या सभी आदानों x ∉ INTERLACE(L1, L2) के लिए हमेशा के लिए लूप का निर्माण करते हैं:

  • एक इनपुट x1 x2 .. xn को देखते हुए। इनपुट x1 x3 x5 .. xn-1 के लिए
  • भागो R1:
  • तो n अजीब है, इनपुट अस्वीकार अन्यथा (n भी है)। यदि R1 हमेशा के लिए loops, तो R हमेशा के लिए loops ("स्वचालित रूप से")। R1 इस इनपुट को खारिज कर दिया है, तो R अपने इनपुट को खारिज कर दिया और खत्म, नहीं तो (यदि R1 अपने इनपुट स्वीकार करता है):
  • भागो इनपुट x2 x4 x6 .. xn के लिए R2। यदि R2 हमेशा के लिए loops, तो R हमेशा के लिए loops। यदि R2 इस इनपुट को अस्वीकार करता है, तो R अपने इनपुट को अस्वीकार करता है, अन्यथा R इसके इनपुट को स्वीकार करता है।

---

पी.एस. आप वास्तव में वहां थे, वास्तव में;)