Understanding Derivations in Chomsky Normal Form (CNF) Grammars

Chomsky Normal Form (CNF) is a simplified form of context-free grammar. A context-free grammar is in Chomsky Normal Form if all its production rules are of one of the following forms:

• \(A \to BC\), where \(A, B\), and \(C\) are non-terminal symbols.
• \(A \to a\), where \(A\) is a non-terminal symbol and \(a\) is a terminal symbol.
• \(S \to \epsilon\), where \(S\) is the start symbol and \(\epsilon\) is the empty string. This rule is only allowed if the language contains the empty string, and \(S\) must not appear on the right-hand side of any other rule.

The question asks about the number of productions needed to derive a non-empty string consisting of exactly \(n\) terminals from a CNF grammar. For a non-empty string (\(n \ge 1\)), the \(S \to \epsilon\) rule is not used in the derivation process itself to produce the final string of terminals.

Derivation Process for a String of \(n\) Terminals in CNF

Consider the structure of a derivation tree for a string of \(n\) terminals in CNF. Each internal node of the tree corresponds to an application of a rule of the form \(A \to BC\). Each leaf node corresponds to an application of a rule of the form \(A \to a\).

To obtain a string of \(n\) terminals, you must ultimately use \(n\) production rules of the form \(A \to a\), one for each terminal symbol in the final string. These \(n\) rules form the 'bottom layer' of the derivation.

Before applying these \(n\) rules, you must have \(n\) non-terminals available at the points where these rules are applied. The derivation starts with a single non-terminal (the start symbol). To get from 1 non-terminal to \(n\) non-terminals that are ready to be converted into terminals, you use rules of the form \(A \to BC\). Each application of \(A \to BC\) takes one non-terminal and replaces it with two non-terminals. This effectively increases the number of non-terminals in the sentential form by one.

Let's track the number of non-terminals:

1. Start: 1 non-terminal (the start symbol).
2. Apply \(A \to BC\): 1 non-terminal replaced by 2, net change is \(+1\) non-terminal.

To obtain \(n\) non-terminals from the initial 1 using only \(A \to BC\) rules, you need to apply this type of rule \(n-1\) times. For example:

• To get 2 non-terminals from 1: Need 1 rule (\(A \to BC\)). Start with 1, apply rule once, get 2.
• To get 3 non-terminals from 1: Need 2 rules (\(A \to BC\)). Start with 1, apply rule 1 (\(\to BC\)), get 2 NTs. Apply rule 2 on one of them (\(\to B'C'\)), get 3 NTs (e.g., \(B B'C'\)).
• To get \(n\) non-terminals from 1: Need \(n-1\) rules of the form \(A \to BC\).

So, the derivation proceeds in two phases:

1. Phase 1: Use \(n-1\) productions of the form \(A \to BC\) to expand the start symbol into a string of \(n\) non-terminals. These applications form the internal nodes of the derivation tree.
2. Phase 2: Use \(n\) productions of the form \(A \to a\) to convert each of the \(n\) non-terminals into the desired terminal symbols. These applications form the leaves of the derivation tree.

The total number of productions used is the sum of the productions from Phase 1 and Phase 2.

Total productions = (Number of \(A \to BC\) rules) + (Number of \(A \to a\) rules)

Total productions = \((n-1) + n = 2n - 1\).

Example Derivation for n=3 Terminals

Let's say we want to derive a string of 3 terminals, like 'abc', from a CNF grammar. A possible sequence of derivations could be:

1. \(S \to AB\) (1 production of type \(A \to BC\)) - Sentential form: \(AB\) (2 non-terminals)
2. \(A \to CD\) (1 production of type \(A \to BC\)) - Sentential form: \(CDB\) (3 non-terminals)
3. \(C \to a\) (1 production of type \(A \to a\)) - Sentential form: \(aDB\) (2 non-terminals, 1 terminal)
4. \(D \to b\) (1 production of type \(A \to a\)) - Sentential form: \(abB\) (1 non-terminal, 2 terminals)
5. \(B \to c\) (1 production of type \(A \to a\)) - Sentential form: \(abc\) (3 terminals)

In this example, we used 2 productions of the form \(A \to BC\) and 3 productions of the form \(A \to a\).

Total productions = \(2 + 3 = 5\).

Using the formula \(2n - 1\) with \(n=3\), we get \(2(3) - 1 = 6 - 1 = 5\). The result matches.

This confirms that \(n-1\) rules of type \(A \to BC\) are needed to expand to \(n\) non-terminals from the start symbol, and \(n\) rules of type \(A \to a\) are needed to convert those \(n\) non-terminals into terminals.

Therefore, to obtain a string of \(n\) terminals from a given Chomsky normal form grammar, the number of productions to be used is \(2n - 1\).

Revision Table: Chomsky Normal Form Grammars

Additional Information: Properties and Uses of CNF Grammars

Chomsky Normal Form is significant in the study of formal languages and automata theory due to several important properties:

• Theorem: Any context-free grammar that does not generate the empty string can be converted into an equivalent grammar in Chomsky Normal Form. If the empty string is generated, an equivalent CNF grammar can be found with the addition of the \(S \to \epsilon\) rule, where \(S\) is the start symbol (under the condition that \(S\) does not appear on the right side of any rule).
• Simplification: CNF provides a simplified and uniform structure for grammar rules, making it easier to develop algorithms for parsing and analysis.
• Parsing Algorithms: Algorithms like the Cocke-Younger-Kasami (CYK) algorithm efficiently determine if a string can be generated by a context-free grammar by assuming the grammar is in CNF. The structure of CNF rules (\(A \to BC\) and \(A \to a\)) directly corresponds to the dynamic programming approach used by CYK.
• Tree Structure: The derivation tree of any non-empty string in a CNF grammar has a binary branching structure (except at the leaves). For a string of length \(n\), the tree has \(n\) leaves (corresponding to the \(A \to a\) rules) and \(n-1\) internal nodes (corresponding to the \(A \to BC\) rules). The number of nodes in such a binary tree with \(n\) leaves is \(2n-1\), which corresponds to the total number of production rule applications.
• Limitations: While useful for theoretical purposes and certain algorithms, CNF grammars can be larger and less intuitive than the original grammars they were converted from.

Understanding the derivation process and the structure imposed by CNF rules is crucial for working with context-free languages and related algorithms.