Match List I with List II

List I		List II
Production Rules		Grammar
A.	S → XY X → 0 Y → 1	I.	Greibach Normal Form
B.	S → aS| bSS |c	II.	Context Sensitive Grammar
C.	S → AB A → 0A | 1A | 0 B → 0A	III.	Chomsky Normal Form
D.	S → aAbc Ab → bA Ac → Bbcc bB → Bb aB → aa | aaA	IV.	S-Grammar

Choose the correct answer from the options given below :

The correct answer is option 3.

Solution :

Important Points 

A context free grammar (CFG) is in Greibach Normal Form (GNF) if all production rules satisfy one of the following conditions:

• A non-terminal generating a terminal (e.g.; X->x)
• A non-terminal generating a terminal followed by any number of non-terminals (e.g.; X->xX1X2…XN)

A context free grammar (CFG) is in Chomsky Normal Form (CNF) if all production rules satisfy one of the following conditions:

• A non-terminal generating a terminal (e.g.; X->x)
• A non-terminal generating two non-terminals (e.g.; X->YZ)
• Start symbol generating ε. (e.g.; S-> ε)

Note : Left side of the given table contains the standard form of the grammar.