Example of Chomsky Normal Form
In Chomsky Normal Form (CNF), the grammar is restricted to production rules having two non-terminals or a single terminal symbol on the right hand side. These rules can be expressed in the form
- A non-terminal symbol generating two non-terminal symbols (A → BC)
- A non-terminal symbol generating a terminal symbol (A → a)
- A start symbol generating ε (S → ε)
Here A,B,C are non-terminal symbols, a is a terminal symbol, S is the start symbol and ε denotes an empty string.
Let us understand Chomsky Normal Form with the help of an example.
Here we have two Grammar G1 and G2 which satisfy the rules for Context free grammar. Now we have to find if they specify the rules for Chomsky Normal Form.
G1 = { S → AB, S → c, A → a, B → b }
G2 = { S → aA, A → a, B → c }
Here we can see that G1 satisfies all the above rules for the Chomsky Normal Form. Hence the Grammar G1 is a Chomsky Normal Form. But for G2, it does not satisfy the above rules due to S → aA (terminal followed by a non-terminal). Hence G2 is not Chomsky Normal Form.
Steps for Converting CFG to CNF
Follow the below steps for converting context-free grammar to Chomsky Normal Form.
Step 1: If the Start symbol S occurs on the right side of a grammar rule, create a new start symbol S’ and a new production or grammar rule S’ → S.
Step 2: Remove null production rules as well as unit production rules from the grammar.
Step 3: Replace each production rule A →B1B2……Bn where n>2, with A→B1C where C→B2…..Bn.
Repeat this step for all production rules of the CFG having two or more symbols on the right side.
Step 4: If the right side of any grammar rule is in the form A→aB where ‘a’ is a terminal symbol and A, B are non-terminals, then the production rule is replaced by A →XB and X →a.
Repeat this step for every production rule of the grammar which is of the form A→aB.
Let’s understand this concept through an example.
Example of Converting CFG to CNF
Convert the given CFG to CNF:
G= { S → ASA | aB,
A → B|S,
B → b|Ɛ
}
Step 1: if we observe the production rules, we can find that in the first two rules starting state S appears right-hand side of the productions. We need to add a new starting state S’ and a new production rule S’ → S.
Step 2: removing null production rules B →Ɛ and A →Ɛ.
After removing B →Ɛ, grammar G
S’ → S,
S → ASA | aB | a ,
A → B | S | Ɛ,
B → b
After removing A →Ɛ, grammar G
S’ → S,
S → ASA | aB | a | AS | SA ,
A → B | S ,
B → b
Removing unit production rules, S’ → S, A → B, and A →S
After removing S’ → S, grammar G
S’ → ASA | aB | a | AS | SA,
S → ASA | aB | a | AS | SA ,
A → B | S ,
B → b
After removing A → B, grammar G
S’ → ASA | aB | a | AS | SA,
S → ASA | aB | a | AS | SA ,
A → b | S ,
B → b
After removing A → S, grammar G
S’ → ASA | aB | a | AS | SA,
S → ASA | aB | a | AS | SA ,
A → b | ASA | aB | a | AS | SA ,
B → b
Step 3: we find some production rules that have more than two symbols on the RHS.
S’ → ASA, S → ASA, A → ASA .
Let’s replace SA by X i.e, X → SA
S’ → AX | aB | a | AS | SA,
S → AX | aB | a | AS | SA ,
A → b | AX | aB | a | AS | SA ,
B → b,
X → SA
Now we will replace terminal symbol a by Y from these rules, S’ → aB, S → aB and A → aB.
Now the grammar G in CNF
S’ → AX | YB | a | AS | SA,
S → AX | YB | a | AS | SA ,
A → b | AX | YB | a | AS | SA ,
B → b,
X → SA,
Y → a
Also, see Greibach Normal Form here
Advantages of Chomsky normal form CNF
Chomsky Normal Form (CNF) has many advantages in formal language theory and algorithm parsing. Some of these advantages include:
- Simple and Standardized grammar
- Efficient Parsing Algorithms
- Less Grammar Size
- Elimination of Empty String Rules
Also read - Arden's theorem
Disadvantages of Chomsky Normal Form (CNF)
- Increased Size: Converting a context-free grammar to Chomsky normal form can result in a significant increase in the number of production rules, leading to larger grammars.
- Loss of Readability: The transformation process to CNF can make grammars less intuitive and harder to understand, especially for humans, due to the proliferation of intermediate variables.
- Complexity of Transformation: Converting a context-free grammar to Chomsky normal form can be computationally expensive, especially for grammars with complex structures or many non-terminal symbols.
- Non-Intuitive Representation: The resulting CNF may not reflect the original structure and semantics of the language, making it less intuitive to reason about the language's syntax and semantics.
Frequently Asked Questions
What is Chomsky's normal form in TOC?
In TOC Chomsky Normal Form is a special form of context-free grammar (CFG). The production rules of Chomsky Normal Form are limited to only single terminal and two non-terminal symbols.
What is Chomsky's theory called?
Chomsky's theory, formed by Noam Chomsky is called Linguistic Theory or Chomskyan Generative Grammar.
Why convert to Chomsky normal form?
Converting to Chomsky Normal Form simplifies parsing algorithms, ensuring that the grammar is more structured and suitable for efficient computations like the CYK algorithm.
What is a unit rule in Chomsky's normal form?
A unit rule in Chomsky Normal Form is a production where a non-terminal produces exactly one other non-terminal (e.g., A → B), which is eliminated during conversion.
Conclusion
This article covered concepts of Chomsky Normal Forms(CNF) and how CFG is converted to CNF.
We highly recommend you to visit the Coding Ninjas Studio library for getting a better hold of the computer fundamentals to crack your dream jobs.
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Code360.