निम्नलिखित में से कौन सा कथन गलत है?

सही उत्तर विकल्प 3 है।

अवधारणा:

विकल्प 1: नियतात्मक पीडीए अस्पष्टता वाली भाषाओं या व्याकरणों को संभाल नहीं सकता।

सच है , नियतात्मक पुश-डाउन ऑटोमेटा उस व्याकरण को हल नहीं करते हैं जिसमें अस्पष्टता की समस्या होती है। नियतात्मक संदर्भ-मुक्त भाषाएँ (DCFL) संदर्भ-मुक्त भाषाओं का एक उचित उपसमूह हैं। वे संदर्भ-मुक्त भाषाएँ हैं जिन्हें नियतात्मक पुशडाउन ऑटोमेटन द्वारा स्वीकार किया जा सकता है। DCFL हमेशा स्पष्ट व्याकरण होते हैं।

विकल्प 2: एनडीपीडीए अस्पष्टता वाली भाषाओं और किसी भी संदर्भ-मुक्त व्याकरण को संभाल सकता है।

सच है, गैर-नियतात्मक पुश-डाउन ऑटोमेटा उस व्याकरण पर निर्भर होते हैं जिसमें अस्पष्टता की समस्या होती है। गैर-नियतात्मक पुशडाउन ऑटोमेटा (NDPDA) संदर्भ-मुक्त भाषाओं का एक उचित उपसमूह है। वे संदर्भ-मुक्त भाषाएँ हैं जिन्हें गैर-नियतात्मक पुशडाउन ऑटोमेटन द्वारा स्वीकार किया जा सकता है। NDPDA हमेशा अस्पष्ट व्याकरण या असंदिग्ध व्याकरण होता है।

विकल्प 3: प्रत्येक NFA को समतुल्य PDA में परिवर्तित नहीं किया जा सकता।

गलत , हर NFA को एक समतुल्य PDA में बदला जा सकता है। हर गैर-नियतात्मक परिमित ऑटोमेटन नियमित व्याकरण को स्वीकार करता है और पुशडाउन ऑटोमेटा संदर्भ-मुक्त व्याकरण को स्वीकार करता है। नियमित व्याकरण संदर्भ-मुक्त व्याकरण का एक उपसमूह है जिसका अर्थ है कि नियमित व्याकरण द्वारा स्वीकार की जाने वाली प्रत्येक भाषा में संदर्भ-मुक्त व्याकरण में समतुल्य पुश डाउन ऑटोमेटा होते हैं।

विकल्प 4: प्रत्येक संदर्भ-मुक्त भाषा का पूरक पुनरावर्ती होता है

सच है,   हर संदर्भ-मुक्त भाषा का पूरक संदर्भ-मुक्त या संदर्भ-मुक्त नहीं होता है क्योंकि यह पूरकता के अंतर्गत बंद नहीं होता है, और हर पुनरावर्ती व्याकरण का पूरक पुनरावर्ती होता है। संदर्भ-मुक्त भाषाएँ पुनरावर्ती भाषाओं का एक उपसमूह हैं, इसलिए हर संदर्भ-मुक्त भाषा का पूरक पुनरावर्ती होना चाहिए।

अतः सही उत्तर है कि प्रत्येक एनएफए को समतुल्य पीडीए में परिवर्तित नहीं किया जा सकता।