Palindromes cannot be recognized by:
2015
Palindromes cannot be recognized by:
- A.
FSM (Finite State Machine)
- B.
PDA (Pushdown Automata)
- C.
Post Machine
- D.
Turing Machine
- E.
Question not attempted
Attempted by 213 students.
Show answer & explanation
Correct answer: A
To determine which automaton cannot recognize palindromes, we analyze the computational power of each model.
Finite State Machine (FSM)
An FSM has a finite number of states and no external memory. It cannot store the entire input string to compare the first half with the reversed second half. Therefore, it cannot recognize palindromes.
Pushdown Automata (PDA)
A PDA uses a stack to store symbols. It can push symbols from the first half of the input and pop them while reading the second half. This allows it to compare each symbol with its counterpart in reverse order, enabling palindrome recognition.
Post Machine
A Post Machine is equivalent in power to a Turing Machine. It can simulate memory operations and compare input symbols from both ends. Thus, it can recognize palindromes.
Turing Machine
A Turing Machine has unbounded memory and can read and write on its tape. It can mark the first and last symbols, compare them, and move inward. This allows it to verify palindromic structure completely.
हिन्दी उत्तर:
पैलिन्ड्रोमों को पहचानने के लिए, प्रत्येक यंत्र की गणनात्मक शक्ति का विश्लेषण करना आवश्यक है।
सीमित अवस्था मशीन (FSM)
एक FSM में सीमित संख्या में अवस्थाएँ होती हैं और कोई बाहरी स्मृति नहीं होती है। यह पूरे इनपुट स्ट्रिंग को स्टोर नहीं कर सकता है और पहले आधे भाग की तुलना दूसरे आधे भाग के विपरीत क्रम में नहीं कर सकता। इसलिए, यह पैलिन्ड्रोमों को पहचान नहीं सकता है।
पुशडाउन ऑटोमेटा (PDA)
एक PDA स्टैक का उपयोग करता है। यह इनपुट के पहले आधे भाग के प्रत्येक प्रतीक को स्टैक में डाल सकता है और दूसरे आधे भाग को पढ़ते समय उन्हें निकाल सकता है। इससे वे प्रत्येक प्रतीक की विपरीत क्रम में तुलना कर सकते हैं, जिससे पैलिन्ड्रोम की पहचान संभव होती है।
पोस्ट मशीन
पोस्ट मशीन ट्यूरिंग मशीन की तुलना में समान शक्ति रखती है। यह स्मृति ऑपरेशन का अनुकरण कर सकती है और इनपुट प्रतीकों की तुलना कर सकती है। इसलिए, यह पैलिन्ड्रोमों को पहचान सकती है।
ट्यूरिंग मशीन
ट्यूरिंग मशीन में असीमित स्मृति होती है और यह अपनी टेप पर पढ़ और लिख सकती है। यह पहले और अंतिम प्रतीकों को चिह्नित कर सकती है, उनकी तुलना कर सकती है, और अंदर की ओर बढ़ सकती है। इससे यह पैलिन्ड्रोमिक संरचना की जाँच कर सकती है।