Theory of Computation & Compilers Previous Year Questions

Explanation

A string x is accepted if the extended transition function, starting from the initial state q0, ends in an accepting state: δ*(q0, x) ∈ A (the set of final states).कोई स्ट्रिंग x तब स्वीकार की जाती है जब विस्तारित transition function, आरंभिक अवस्था q0 से शुरू होकर, किसी स्वीकार करने वाली अवस्था पर समाप्त हो: δ*(q0, x) ∈ A (अंतिम अवस्थाओं का समुच्चय)।

Explanation

Right-linear grammars (A → aB or A → a) are exactly the regular grammars, so every right-linear grammar generates a regular language.Right-linear grammars (A → aB या A → a) ठीक वही regular grammars हैं, इसलिए हर right-linear grammar एक regular भाषा उत्पन्न करता है।

Explanation

The complement of L is Σ* − L, so it can be defined only once the alphabet Σ is fixed.L का complement Σ* − L होता है, इसलिए इसे तभी परिभाषित किया जा सकता है जब वर्णमाला Σ तय हो।

Explanation

Every rule adds one 0 and one 1 together (0S1, 1S0) or concatenates such strings (SS), so all generated strings have equal numbers of 0s and 1s.

Explanation

Recursively enumerable languages are Type 0 in the Chomsky hierarchy, generated by unrestricted grammars and recognised by Turing machines.

Explanation

A universal Turing machine takes the description of any other TM and its input and simulates it, so it is a reprogrammable (stored-program) Turing machine.

Explanation

Recursively enumerable languages are Type 0 in the Chomsky hierarchy. They are generated by unrestricted grammars and recognised by Turing machines. Types 1, 2 and 3 are context-sensitive, context-free and regular.Recursively enumerable भाषाएँ Chomsky पदानुक्रम में Type 0 हैं। वे unrestricted व्याकरणों से बनती हैं और Turing मशीनों से पहचानी जाती हैं। Type 1, 2 और 3 क्रमशः context-sensitive, context-free और regular हैं।

Explanation

Not every non-deterministic PDA can be converted into a deterministic one, because DPDAs accept only the deterministic context-free languages. NFA-to-DFA and NTM-to-DTM conversions are always possible, and every regular grammar is already context-free.हर non-deterministic PDA को deterministic में नहीं बदला जा सकता, क्योंकि DPDA केवल deterministic context-free भाषाएँ स्वीकार करते हैं। NFA से DFA और NTM से DTM में रूपांतरण हमेशा संभव है, और हर regular व्याकरण पहले से context-free है।

Explanation

In the Chomsky hierarchy, Type 0 is recursively enumerable, Type 1 is context-sensitive, Type 2 is context-free and Type 3 is regular.Chomsky पदानुक्रम में Type 0 recursively enumerable, Type 1 context-sensitive, Type 2 context-free और Type 3 regular है।

Explanation

A universal Turing machine reads another TM's description plus its input from the tape and simulates it. In effect it is a programmable, reprogrammable Turing machine, the model for stored-program computers.Universal Turing मशीन टेप से किसी दूसरी TM का विवरण और उसका इनपुट पढ़ती है और उसका अनुकरण करती है। असल में यह प्रोग्राम योग्य, पुनः प्रोग्राम की जा सकने वाली Turing मशीन है, जो stored-program कंप्यूटर का मॉडल है।

Explanation

Multi-tape, multi-head and non-deterministic Turing machines are all extensions of the basic TM, and none of them adds computational power.Multi-tape, multi-head और non-deterministic Turing मशीन सब मूल TM के विस्तार हैं, और कोई भी गणनात्मक शक्ति नहीं बढ़ाता।

Explanation

"automata" has 8 characters. A DFA needs one state before reading any character plus one after each character: 8 + 1 = 9 states (a dead state is not counted)."automata" में 8 अक्षर हैं। DFA को कोई अक्षर पढ़ने से पहले एक अवस्था और हर अक्षर के बाद एक अवस्था चाहिए: 8 + 1 = 9 अवस्थाएँ (dead state गिनी नहीं जाती)।

Explanation

Every regular language is context-free, but not every context-free language is regular (e.g. a^n b^n), so statement (b) is false. Note that (a) is also false, since recursive languages need not be regular.हर regular भाषा context-free होती है, पर हर context-free भाषा regular नहीं होती (जैसे a^n b^n), इसलिए कथन (b) असत्य है। ध्यान दें कि (a) भी असत्य है, क्योंकि recursive भाषाएँ regular होना ज़रूरी नहीं।

Explanation

b(a+b)*bba starts with b, allows any string of a and b in the middle, and ends with bba. The other expressions start with a, so they are wrong.b(a+b)*bba b से शुरू होता है, बीच में a और b की कोई भी स्ट्रिंग आने देता है और bba पर समाप्त होता है। बाकी व्यंजक a से शुरू होते हैं, इसलिए गलत हैं।

Explanation

Recognising palindromes requires remembering an unbounded first half to compare with the second half. A DFA has finite memory, so palindromes are not regular; a PDA is needed.Palindrome पहचानने के लिए पहली अनबाउंडेड आधी स्ट्रिंग याद रखनी पड़ती है ताकि दूसरी आधी से तुलना हो। DFA की मेमोरी सीमित है, इसलिए palindrome regular नहीं हैं; PDA चाहिए।

Explanation

A Turing machine halts only on entering an accept state or a reject state. On some inputs it may also loop forever.Turing मशीन केवल accept अवस्था या reject अवस्था में पहुँचने पर रुकती है। कुछ इनपुट पर वह हमेशा के लिए लूप में भी जा सकती है।

Explanation

An NFA with 5 states plus the initial state has 6 states. The subset construction can produce up to 2⁶ = 64 DFA states.5 अवस्थाओं के साथ प्रारंभिक अवस्था जोड़ने पर NFA में 6 अवस्थाएँ हैं। Subset construction से अधिकतम 2⁶ = 64 DFA अवस्थाएँ बन सकती हैं।

Explanation

The complement of L is Σ* - L, so it can be defined only once the alphabet Σ is fixed.L का पूरक Σ* - L है, इसलिए इसे तभी परिभाषित किया जा सकता है जब वर्णमाला Σ तय हो।

Explanation

A language is regular exactly when some DFA (equivalently an NFA or regular expression) accepts it.कोई भाषा तभी regular होती है जब कोई DFA (या इसके समतुल्य NFA अथवा regular expression) उसे स्वीकार करे।

Explanation

5 states plus the initial state is 6 NFA states. Subset construction can give at most 2^6 = 64 DFA states.5 अवस्थाएँ और प्रारंभिक अवस्था मिलाकर 6 NFA अवस्थाएँ हुईं। Subset construction से अधिकतम 2^6 = 64 DFA अवस्थाएँ बन सकती हैं।