Match the LIST-I with LIST-II

LIST - I		LIST - II
A.	Type - 0 grammar	I.	Linear Grammar
B.	Type - 1 grammar	II.	GNF
C.	Type - 2 grammar	III.	x → y, |x| < |y|; x y ∈ {V ∪ T}*
D.	Type - 3 grammar	IV.	Recursively Enumerable

Choose the correct answer from the options given below:

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