According to Chomsky hierarchy, which of the following is recognized by…

2025

According to Chomsky hierarchy, which of the following is recognized by Recursively Enumerable language?

  1. A.

    Type 0

  2. B.

    Type 1

  3. C.

    Type 2

  4. D.

    Type 3

Attempted by 92 students.

Show answer & explanation

Correct answer: A

In the Chomsky hierarchy, Recursively Enumerable languages are recognized by Type 0 grammars. These grammars have no restrictions on production rules and are recognized by Turing machines. This makes them the most powerful class in the hierarchy. Type 1 (context-sensitive), Type 2 (context-free), and Type 3 (regular) languages are all subsets of Type 0 languages, but they are not equivalent. Therefore, only Type 0 languages are fully recognized by Recursively Enumerable languages.

हिन्दी उत्तर:

चॉम्स्की हाइरार्की में, रिकर्सिवली एनुमरेबल भाषाएँ टाइप 0 वाक्यांशिक नियमों द्वारा पहचानी जाती हैं। ये वाक्यांशिक नियम उत्पादन नियमों पर कोई प्रतिबंध नहीं रखते और ट्यूरिंग मशीन द्वारा पहचाने जाते हैं। इससे यह श्रेणी सबसे शक्तिशाली होती है। टाइप 1 (संदर्भ-संवेदी), टाइप 2 (संदर्भ-मुक्त) और टाइप 3 (नियमित) भाषाएँ टाइप 0 भाषाओं के उपसमूह हैं, लेकिन वे बराबर नहीं हैं। इसलिए, केवल टाइप 0 भाषाएँ रिकर्सिवली एनुमरेबल भाषाओं द्वारा पहचानी जाती हैं।

Explore the full course: Bpsc