Solution

Question: Match the following grammar types (Chomsky Hierarchy) with their correct definitions:

Explanation:

• Type-0 Grammar: Also called Unrestricted Grammar. Recognized by Turing Machines. These languages are Recursively Enumerable. → IV
• Type-1 Grammar: Context-Sensitive Grammar. Rules are of the form x → y where |x| ≤ |y| and both sides are strings over variables and terminals. → III
• Type-2 Grammar: Context-Free Grammar. Can be converted into Greibach Normal Form (GNF). → II
• Type-3 Grammar: Regular Grammar. A subset of CFGs where production rules are linear. → I

Correct Matching:

• A → IV
• B → III
• C → II
• D → I

Correct Answer: Option 4) A - IV, B - III, C - II, D - I