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:
1.A - I, B - II, C - III, D - IV
2.A - II, B - I, C - III, D - IV
3.A - III, B - II, C - IV, D - I
4.A - IV, B - III, C - lI, D - I ✓ Correct
Solution
Question: Match the following grammar types (Chomsky Hierarchy) with their correct definitions:
| List I (Grammar Type) |
List II (Definition) |
| A. Type-0 Grammar |
IV. Recursively Enumerable |
| B. Type-1 Grammar |
III. x → y, |x| ≤ |y|; x, y ∈ {V ∪ T}* |
| C. Type-2 Grammar |
II. GNF |
| D. Type-3 Grammar |
I. Linear Grammar |
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