Chomsky Normal Form (CNF)
- Any context free grammar G = (V, T, S, P) with λ ∉ L(G) has an equivalent grammar in Chomsky Normal Form.
- There are two types of productions in CNF grammar:
<variable>→ <terminal>
<variable>→ <variable><variable>
- In RHS of every production of the CNF grammar contain only two non terminals or a single terminal.
A → BC
A → a
- CNF is also called as binary standard form.
- The number of productions are required for generating x-length string from the given CNF context
free grammar is: (2x – 1)
Example: Consider a context free grammar in Chomsky’s Normal Form
S → AB
A → a
B → b
Number of productions used = 3 i.e. 2x – 1 where x = length of string.
- Let ‘G’ be the given CNF grammar and ‘T ’ be the derivation tree for some string ‘x’ in G. If the length
of the longest path is equal to k then yield length ≤ 2k – 1. - For the generation of ‘l’ length yield, the minimum height of the derivation tree for the given CNF
context free grammar - Let h be the minimum height of the derivation tree, which gives yield of length ‘l’.
l = 2h – 1 ⇒ h – 1 = log2 l ⇒ h = log2 l + 1.
- Let ‘G’ be the given CFG without null productions and unit productions and ‘k’ be the maximum
number of symbols on the right hand side of any production. - Then the equivalent CNF contain a maximum of: (k – 1)|P| + |T| productions.
where, |P| = the number of productions in ‘G’, |T| = the number of terminals, k = maximum number of symbols on right hand side.
Dear Aspirants,
Your preparation for GATE, ESE, PSUs, and AE/JE is now smarter than ever — thanks to the MADE EASY YouTube channel.
This is not just a channel, but a complete strategy for success, where you get toppers strategies, PYQ–GTQ discussions, current affairs updates, and important job-related information, all delivered by the country’s best teachers and industry experts.
If you also want to stay one step ahead in the race to success, subscribe to MADE EASY on YouTube and stay connected with us on social media.
MADE EASY — where preparation happens with confidence.
MADE EASY is a well-organized institute, complete in all aspects, and provides quality guidance for both written and personality tests. MADE EASY has produced top-ranked students in ESE, GATE, and various public sector exams. The publishing team regularly writes exam-related blogs based on conversations with the faculty, helping students prepare effectively for their exams.
