Chomsky Normal Form

Reading

Jurafsky and Martin (2023, Ch. 17–18) and Hopcroft and Ullman (1979) on context-free grammars, normal forms, and parsing.

A context-free rule may have any finite string of symbols on its right side. The CKY algorithm is simpler because it assumes a more restricted grammar. So what restriction does CKY need? We will call it Chomsky Normal Form (CNF) (Chomsky 1963).

Definition

A CFG is in CNF when every rule has one of the following forms:

\[ A\rightarrow BC \qquad\text{or}\qquad A\rightarrow a, \]

where $A,B,C\in V$ and $a\in\Sigma$. If $\epsilon\in\mathbb{L}(G)$, we also permit $S\rightarrow\epsilon$ as long as $S$ does not occur on the right side of a rule.

The first form combines exactly two constituents; the second introduces exactly one terminal. Thus, a CNF parse is binary branching above the terminals.

Converting a grammar

Every context-free language has a CFG in CNF, with the qualification about $\epsilon$ just stated. We construct one in four stages:

eliminate epsilon rules while preserving whether the start variable derives $\epsilon$;
eliminate unit rules of the form $A\rightarrow B$;
replace terminals in longer right sides with new variables; and
split right sides longer than two symbols into binary rules.

Each stage preserves the generated language. It need not preserve the original trees node for node, because the construction introduces variables whose only purpose is to satisfy the normal form.

Why conversion preserves the language

Why should these four changes leave the language alone? We can answer the question one stage at a time. At each stage, we show how to translate an old derivation into a new one and a new derivation back into an old one.

Epsilon rules

Call a variable nullable when it derives $\epsilon$. Suppose the old grammar contains

\[A\rightarrow X_1X_2\cdots X_k.\]

For every selection of nullable occurrences on the right side, add a rule that omits exactly those occurrences. If $X_2$ and $X_4$ are nullable, for instance, we add

\[A\rightarrow X_1X_3X_5\cdots X_k.\]

To translate an old derivation into the new grammar, inspect each use of the original rule. Whenever a child subtree derives $\epsilon$, use the shortened rule that omits that child; retain every child with a nonempty yield. The new derivation has the same terminal yield.

For the reverse translation, suppose a new derivation uses a shortened rule. Restore the omitted nullable variables in their original positions and attach one of their old epsilon derivations. This reconstructs an old derivation with the same yield. The only complete string that cannot be handled by omitting a child is $\epsilon$ itself, so a fresh start variable retains $S_{new}\rightarrow\epsilon$ exactly when the old start variable was nullable.

Unit rules

A unit chain has the form

\[A\Rightarrow B_1\Rightarrow\cdots\Rightarrow B_m\Rightarrow\gamma,\]

where the intermediate steps use unit rules and the last rule is not a unit rule. Compute the unit closure: record $(A,B)$ whenever $A\Rightarrow^*B$ using only unit rules. Then, for every recorded pair and every nonunit rule $B\rightarrow\gamma$, add $A\rightarrow\gamma$.

An old derivation is translated by replacing each maximal unit chain with its one-step shortcut. A new shortcut $A\rightarrow\gamma$ is translated back by restoring the recorded chain from $A$ to $B$ and then using $B\rightarrow\gamma$. The two derivations have the same terminal yield.

Terminals in longer rules

Suppose a terminal $a$ occurs in a right side of length at least two. Introduce a fresh variable $T_a$ with rule $T_a\rightarrow a$, and replace that occurrence of $a$ by $T_a$. For instance,

\[ A\rightarrow aB \qquad\text{becomes}\qquad A\rightarrow T_aB, \quad T_a\rightarrow a. \]

Every use of the old rule becomes two levels in the new tree, with $T_a\Rightarrow a$. Conversely, collapsing each $T_a\Rightarrow a$ recovers the old rule. The extra node changes the tree but not its frontier yield.

Binarization

Finally, replace a long rule such as

\[A\rightarrow X_1X_2X_3X_4\]

with a binary chain:

\[ \begin{aligned} A&\rightarrow X_1C_1,\\ C_1&\rightarrow X_2C_2,\\ C_2&\rightarrow X_3X_4. \end{aligned} \]

Expanding the fresh continuation variables yields $X_1X_2X_3X_4$ in the same order, so one old rule application can be expanded into the new chain. Conversely, each continuation variable is fresh and occurs only in its designated chain. Collapsing the chain thus recovers the old rule application. Again, the derivation tree changes but its terminal yield does not.

After the four stages, every non-start epsilon rule, every unit rule, every terminal in a longer right side, and every right side longer than two has been removed. The remaining rules have the CNF shapes, and the four bidirectional simulations prove that the final grammar has the same string language as the original.

The following implementation uses Python 3.14’s generic-function and deferred-annotation syntax. In particular, the return annotation on to_cnf can refer to the class being defined without quotation marks.

Load the CFG representation

import sys

sys.path.insert(0, "_code")
from grammar import ContextFreeGrammar, Rule

from collections.abc import Iterator
from itertools import combinations


def subsets[T](items: tuple[T, ...]) -> Iterator[tuple[T, ...]]:
    """Yield every subset of ``items`` as a tuple."""
    for size in range(len(items) + 1):
        yield from combinations(items, size)


class ContextFreeGrammar(ContextFreeGrammar):
    """A context-free grammar with conversion to CNF."""

    def to_cnf(self) -> ContextFreeGrammar:
        """Return a weakly equivalent grammar in Chomsky Normal Form."""
        alphabet = self.alphabet.copy()
        variables = self.variables.copy()
        rules = self.rules().copy()

        start = self._fresh_variable(
            f"{self.start_variable}_START",
            variables | alphabet,
        )
        variables.add(start)
        rules.add(Rule(start, self.start_variable))

        nullable = self._nullable_variables(rules)
        rules = self._without_epsilon_rules(rules, nullable)
        if start in nullable:
            rules.add(Rule(start))

        rules = self._without_unit_rules(rules, variables)
        rules, variables = self._separate_terminals(
            rules, variables, alphabet
        )
        rules, variables = self._binarize(
            rules,
            variables,
            alphabet,
        )

        grammar = ContextFreeGrammar(
            alphabet=alphabet,
            variables=variables,
            rules=rules,
            start_variable=start,
        )
        if not grammar.is_cnf:
            raise RuntimeError("CNF conversion produced an invalid grammar")
        return grammar

    @staticmethod
    def _fresh_variable(prefix: str, variables: set[str]) -> str:
        """Return a variable name not contained in ``variables``."""
        candidate = prefix
        index = 1
        while candidate in variables:
            candidate = f"{prefix}_{index}"
            index += 1
        return candidate

    @staticmethod
    def _nullable_variables(rules: set[Rule]) -> set[str]:
        """Return the variables that derive the empty string."""
        nullable = {
            rule.left_side for rule in rules if not rule.right_side
        }

        while True:
            inferred = {
                rule.left_side
                for rule in rules
                if all(symbol in nullable for symbol in rule.right_side)
            }
            new_nullable = nullable | inferred
            if new_nullable == nullable:
                return nullable
            nullable = new_nullable

    @staticmethod
    def _without_epsilon_rules(
        rules: set[Rule], nullable: set[str]
    ) -> set[Rule]:
        """Remove epsilon rules and add the required shortened rules."""
        new_rules: set[Rule] = set()

        for rule in rules:
            if not rule.right_side:
                continue

            nullable_positions = tuple(
                index
                for index, symbol in enumerate(rule.right_side)
                if symbol in nullable
            )
            for omitted in subsets(nullable_positions):
                right_side = tuple(
                    symbol
                    for index, symbol in enumerate(rule.right_side)
                    if index not in omitted
                )
                if right_side:
                    new_rules.add(Rule(rule.left_side, *right_side))

        return new_rules

    @staticmethod
    def _without_unit_rules(
        rules: set[Rule], variables: set[str]
    ) -> set[Rule]:
        """Remove rules whose right side is a single variable."""
        unit_pairs = {(variable, variable) for variable in variables}
        direct_pairs = {
            (rule.left_side, rule.right_side[0])
            for rule in rules
            if len(rule.right_side) == 1
            and rule.right_side[0] in variables
        }

        while True:
            inferred = {
                (left, target)
                for left, middle in unit_pairs
                for source, target in direct_pairs
                if middle == source
            }
            new_pairs = unit_pairs | direct_pairs | inferred
            if new_pairs == unit_pairs:
                break
            unit_pairs = new_pairs

        nonunit_rules = {
            rule
            for rule in rules
            if not (
                len(rule.right_side) == 1
                and rule.right_side[0] in variables
            )
        }
        return {
            Rule(left, *rule.right_side)
            for left, source in unit_pairs
            for rule in nonunit_rules
            if rule.left_side == source
        }

    @classmethod
    def _separate_terminals(
        cls,
        rules: set[Rule],
        variables: set[str],
        alphabet: set[str],
    ) -> tuple[set[Rule], set[str]]:
        """Replace terminals in nonlexical rules with new variables."""
        new_variables = variables.copy()
        terminal_variables: dict[str, str] = {}
        new_rules: set[Rule] = set()

        for rule in sorted(rules, key=str):
            if len(rule.right_side) < 2:
                new_rules.add(rule)
                continue

            right_side: list[str] = []
            for symbol in rule.right_side:
                if symbol not in alphabet:
                    right_side.append(symbol)
                    continue

                if symbol not in terminal_variables:
                    variable = cls._fresh_variable(
                        "TERMINAL",
                        new_variables | alphabet,
                    )
                    new_variables.add(variable)
                    terminal_variables[symbol] = variable
                    new_rules.add(Rule(variable, symbol))
                right_side.append(terminal_variables[symbol])

            new_rules.add(Rule(rule.left_side, *right_side))

        return new_rules, new_variables

    @classmethod
    def _binarize(
        cls,
        rules: set[Rule],
        variables: set[str],
        alphabet: set[str],
    ) -> tuple[set[Rule], set[str]]:
        """Replace right sides longer than two with binary chains."""
        new_variables = variables.copy()
        new_rules: set[Rule] = set()

        for rule in sorted(rules, key=str):
            left_side = rule.left_side
            right_side = list(rule.right_side)

            while len(right_side) > 2:
                continuation = cls._fresh_variable(
                    "BINARY",
                    new_variables | alphabet,
                )
                new_variables.add(continuation)
                new_rules.add(Rule(left_side, right_side[0], continuation))
                left_side = continuation
                right_side = right_side[1:]

            new_rules.add(Rule(left_side, *right_side))

        return new_rules, new_variables

    @property
    def is_cnf(self) -> bool:
        """Whether every rule satisfies the CNF restrictions."""
        has_start_epsilon = Rule(self.start_variable) in self.rules()
        if has_start_epsilon and any(
            self.start_variable in rule.right_side
            for rule in self.rules()
        ):
            return False

        for rule in self.rules():
            if not rule.right_side:
                if rule.left_side != self.start_variable:
                    return False
            elif len(rule.right_side) == 1:
                if rule.right_side[0] not in self.alphabet:
                    return False
            elif len(rule.right_side) == 2:
                if not all(
                    symbol in self.variables for symbol in rule.right_side
                ):
                    return False
            else:
                return False
        return True

A conversion

Consider a grammar containing the rules

\[ \begin{aligned} \text{Word} &\rightarrow \text{Prefix}\;\text{Adjective}\;\text{Suffix} \\ \text{Prefix} &\rightarrow \text{un} \\ \text{Adjective} &\rightarrow \text{happy} \\ \text{Suffix} &\rightarrow \text{ness}. \end{aligned} \]

The first rule is too long for CNF. Binarization replaces it with a chain whose new variable records the unexpanded remainder:

\[ \begin{aligned} \text{Word} &\rightarrow \text{Prefix}\;\text{BINARY} \\ \text{BINARY} &\rightarrow \text{Adjective}\;\text{Suffix}. \end{aligned} \]

grammar = ContextFreeGrammar(
    alphabet={"un", "happy", "ness"},
    variables={"Word", "Prefix", "Adjective", "Suffix"},
    rules={
        Rule("Word", "Prefix", "Adjective", "Suffix"),
        Rule("Prefix", "un"),
        Rule("Adjective", "happy"),
        Rule("Suffix", "ness"),
    },
    start_variable="Word",
)

cnf_grammar = grammar.to_cnf()
assert cnf_grammar.is_cnf

Question

Does CNF conversion preserve the original morphological tree exactly?

Answer

No. It preserves the generated strings, but binarization adds administrative variables such as BINARY. To recover the original analysis, we must remove or collapse those nodes after parsing.

CNF gives the next algorithm its local combination rule: every nonterminal over a longer span must have been formed by one binary rule at one split point.

References

Chomsky, Noam. 1963. “Formal Properties of Grammars.” In Handbook of Mathematical Psychology, edited by R. Duncan Luce, Robert R. Bush, and Eugene Galanter, vol. 2. John Wiley & Sons.

Hopcroft, John E., and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.

Jurafsky, Daniel, and James H. Martin. 2023. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. 3rd ed. https://web.stanford.edu/~jurafsky/slp3/old_jan23/ed3book.pdf.

--- title: Chomsky Normal Form bibliography: ../references.bib jupyter: python3 --- ::: {.callout-tip} ## Reading @jurafsky_speech_2023[Ch. 17–18] and @hopcroft_introduction_1979 on context-free grammars, normal forms, and parsing. ::: A context-free rule may have any finite string of symbols on its right side. The CKY algorithm is simpler because it assumes a more restricted grammar. So what restriction does CKY need? We will call it **Chomsky Normal Form** (CNF) [@chomsky_formal_1963]. ## Definition A CFG is in CNF when every rule has one of the following forms: $$ A\rightarrow BC \qquad\text{or}\qquad A\rightarrow a, $$ where $A,B,C\in V$ and $a\in\Sigma$. If $\epsilon\in\mathbb{L}(G)$, we also permit $S\rightarrow\epsilon$ as long as $S$ does not occur on the right side of a rule. The first form combines exactly two constituents; the second introduces exactly one terminal. Thus, a CNF parse is binary branching above the terminals. ## Converting a grammar Every context-free language has a CFG in CNF, with the qualification about $\epsilon$ just stated. We construct one in four stages: 1. eliminate epsilon rules while preserving whether the start variable derives $\epsilon$; 2. eliminate unit rules of the form $A\rightarrow B$; 3. replace terminals in longer right sides with new variables; and 4. split right sides longer than two symbols into binary rules. Each stage preserves the generated language. It need not preserve the original trees node for node, because the construction introduces variables whose only purpose is to satisfy the normal form. ## Why conversion preserves the language Why should these four changes leave the language alone? We can answer the question one stage at a time. At each stage, we show how to translate an old derivation into a new one and a new derivation back into an old one. ### Epsilon rules Call a variable *nullable* when it derives $\epsilon$. Suppose the old grammar contains $$A\rightarrow X_1X_2\cdots X_k.$$ For every selection of nullable occurrences on the right side, add a rule that omits exactly those occurrences. If $X_2$ and $X_4$ are nullable, for instance, we add $$A\rightarrow X_1X_3X_5\cdots X_k.$$ To translate an old derivation into the new grammar, inspect each use of the original rule. Whenever a child subtree derives $\epsilon$, use the shortened rule that omits that child; retain every child with a nonempty yield. The new derivation has the same terminal yield. For the reverse translation, suppose a new derivation uses a shortened rule. Restore the omitted nullable variables in their original positions and attach one of their old epsilon derivations. This reconstructs an old derivation with the same yield. The only complete string that cannot be handled by omitting a child is $\epsilon$ itself, so a fresh start variable retains $S_{new}\rightarrow\epsilon$ exactly when the old start variable was nullable. ### Unit rules A unit chain has the form $$A\Rightarrow B_1\Rightarrow\cdots\Rightarrow B_m\Rightarrow\gamma,$$ where the intermediate steps use unit rules and the last rule is not a unit rule. Compute the unit closure: record $(A,B)$ whenever $A\Rightarrow^*B$ using only unit rules. Then, for every recorded pair and every nonunit rule $B\rightarrow\gamma$, add $A\rightarrow\gamma$. An old derivation is translated by replacing each maximal unit chain with its one-step shortcut. A new shortcut $A\rightarrow\gamma$ is translated back by restoring the recorded chain from $A$ to $B$ and then using $B\rightarrow\gamma$. The two derivations have the same terminal yield. ### Terminals in longer rules Suppose a terminal $a$ occurs in a right side of length at least two. Introduce a fresh variable $T_a$ with rule $T_a\rightarrow a$, and replace that occurrence of $a$ by $T_a$. For instance, $$ A\rightarrow aB \qquad\text{becomes}\qquad A\rightarrow T_aB, \quad T_a\rightarrow a. $$ Every use of the old rule becomes two levels in the new tree, with $T_a\Rightarrow a$. Conversely, collapsing each $T_a\Rightarrow a$ recovers the old rule. The extra node changes the tree but not its frontier yield. ### Binarization Finally, replace a long rule such as $$A\rightarrow X_1X_2X_3X_4$$ with a binary chain: $$ \begin{aligned} A&\rightarrow X_1C_1,\\ C_1&\rightarrow X_2C_2,\\ C_2&\rightarrow X_3X_4. \end{aligned} $$ Expanding the fresh continuation variables yields $X_1X_2X_3X_4$ in the same order, so one old rule application can be expanded into the new chain. Conversely, each continuation variable is fresh and occurs only in its designated chain. Collapsing the chain thus recovers the old rule application. Again, the derivation tree changes but its terminal yield does not. After the four stages, every non-start epsilon rule, every unit rule, every terminal in a longer right side, and every right side longer than two has been removed. The remaining rules have the CNF shapes, and the four bidirectional simulations prove that the final grammar has the same string language as the original. The following implementation uses Python 3.14's generic-function and deferred-annotation syntax. In particular, the return annotation on `to_cnf` can refer to the class being defined without quotation marks. ```{python} #| code-fold: true #| code-summary: Load the CFG representation import sys sys.path.insert(0, "_code") from grammar import ContextFreeGrammar, Rule ``` ```{python} from collections.abc import Iterator from itertools import combinations def subsets[T](items: tuple[T, ...]) -> Iterator[tuple[T, ...]]: """Yield every subset of ``items`` as a tuple.""" for size in range(len(items) + 1): yield from combinations(items, size) class ContextFreeGrammar(ContextFreeGrammar): """A context-free grammar with conversion to CNF.""" def to_cnf(self) -> ContextFreeGrammar: """Return a weakly equivalent grammar in Chomsky Normal Form.""" alphabet = self.alphabet.copy() variables = self.variables.copy() rules = self.rules().copy() start = self._fresh_variable( f"{self.start_variable}_START", variables | alphabet, ) variables.add(start) rules.add(Rule(start, self.start_variable)) nullable = self._nullable_variables(rules) rules = self._without_epsilon_rules(rules, nullable) if start in nullable: rules.add(Rule(start)) rules = self._without_unit_rules(rules, variables) rules, variables = self._separate_terminals( rules, variables, alphabet ) rules, variables = self._binarize( rules, variables, alphabet, ) grammar = ContextFreeGrammar( alphabet=alphabet, variables=variables, rules=rules, start_variable=start, ) if not grammar.is_cnf: raise RuntimeError("CNF conversion produced an invalid grammar") return grammar @staticmethod def _fresh_variable(prefix: str, variables: set[str]) -> str: """Return a variable name not contained in ``variables``.""" candidate = prefix index = 1 while candidate in variables: candidate = f"{prefix}_{index}" index += 1 return candidate @staticmethod def _nullable_variables(rules: set[Rule]) -> set[str]: """Return the variables that derive the empty string.""" nullable = { rule.left_side for rule in rules if not rule.right_side } while True: inferred = { rule.left_side for rule in rules if all(symbol in nullable for symbol in rule.right_side) } new_nullable = nullable | inferred if new_nullable == nullable: return nullable nullable = new_nullable @staticmethod def _without_epsilon_rules( rules: set[Rule], nullable: set[str] ) -> set[Rule]: """Remove epsilon rules and add the required shortened rules.""" new_rules: set[Rule] = set() for rule in rules: if not rule.right_side: continue nullable_positions = tuple( index for index, symbol in enumerate(rule.right_side) if symbol in nullable ) for omitted in subsets(nullable_positions): right_side = tuple( symbol for index, symbol in enumerate(rule.right_side) if index not in omitted ) if right_side: new_rules.add(Rule(rule.left_side, *right_side)) return new_rules @staticmethod def _without_unit_rules( rules: set[Rule], variables: set[str] ) -> set[Rule]: """Remove rules whose right side is a single variable.""" unit_pairs = {(variable, variable) for variable in variables} direct_pairs = { (rule.left_side, rule.right_side[0]) for rule in rules if len(rule.right_side) == 1 and rule.right_side[0] in variables } while True: inferred = { (left, target) for left, middle in unit_pairs for source, target in direct_pairs if middle == source } new_pairs = unit_pairs | direct_pairs | inferred if new_pairs == unit_pairs: break unit_pairs = new_pairs nonunit_rules = { rule for rule in rules if not ( len(rule.right_side) == 1 and rule.right_side[0] in variables ) } return { Rule(left, *rule.right_side) for left, source in unit_pairs for rule in nonunit_rules if rule.left_side == source } @classmethod def _separate_terminals( cls, rules: set[Rule], variables: set[str], alphabet: set[str], ) -> tuple[set[Rule], set[str]]: """Replace terminals in nonlexical rules with new variables.""" new_variables = variables.copy() terminal_variables: dict[str, str] = {} new_rules: set[Rule] = set() for rule in sorted(rules, key=str): if len(rule.right_side) < 2: new_rules.add(rule) continue right_side: list[str] = [] for symbol in rule.right_side: if symbol not in alphabet: right_side.append(symbol) continue if symbol not in terminal_variables: variable = cls._fresh_variable( "TERMINAL", new_variables | alphabet, ) new_variables.add(variable) terminal_variables[symbol] = variable new_rules.add(Rule(variable, symbol)) right_side.append(terminal_variables[symbol]) new_rules.add(Rule(rule.left_side, *right_side)) return new_rules, new_variables @classmethod def _binarize( cls, rules: set[Rule], variables: set[str], alphabet: set[str], ) -> tuple[set[Rule], set[str]]: """Replace right sides longer than two with binary chains.""" new_variables = variables.copy() new_rules: set[Rule] = set() for rule in sorted(rules, key=str): left_side = rule.left_side right_side = list(rule.right_side) while len(right_side) > 2: continuation = cls._fresh_variable( "BINARY", new_variables | alphabet, ) new_variables.add(continuation) new_rules.add(Rule(left_side, right_side[0], continuation)) left_side = continuation right_side = right_side[1:] new_rules.add(Rule(left_side, *right_side)) return new_rules, new_variables @property def is_cnf(self) -> bool: """Whether every rule satisfies the CNF restrictions.""" has_start_epsilon = Rule(self.start_variable) in self.rules() if has_start_epsilon and any( self.start_variable in rule.right_side for rule in self.rules() ): return False for rule in self.rules(): if not rule.right_side: if rule.left_side != self.start_variable: return False elif len(rule.right_side) == 1: if rule.right_side[0] not in self.alphabet: return False elif len(rule.right_side) == 2: if not all( symbol in self.variables for symbol in rule.right_side ): return False else: return False return True ``` ## A conversion Consider a grammar containing the rules $$ \begin{aligned} \text{Word} &\rightarrow \text{Prefix}\;\text{Adjective}\;\text{Suffix} \\ \text{Prefix} &\rightarrow \text{un} \\ \text{Adjective} &\rightarrow \text{happy} \\ \text{Suffix} &\rightarrow \text{ness}. \end{aligned} $$ The first rule is too long for CNF. Binarization replaces it with a chain whose new variable records the unexpanded remainder: $$ \begin{aligned} \text{Word} &\rightarrow \text{Prefix}\;\text{BINARY} \\ \text{BINARY} &\rightarrow \text{Adjective}\;\text{Suffix}. \end{aligned} $$ ```{python} grammar = ContextFreeGrammar( alphabet={"un", "happy", "ness"}, variables={"Word", "Prefix", "Adjective", "Suffix"}, rules={ Rule("Word", "Prefix", "Adjective", "Suffix"), Rule("Prefix", "un"), Rule("Adjective", "happy"), Rule("Suffix", "ness"), }, start_variable="Word", ) cnf_grammar = grammar.to_cnf() assert cnf_grammar.is_cnf ``` ::: {.callout-caution} ## Question Does CNF conversion preserve the original morphological tree exactly? ::: ::: {.callout-tip collapse=true} ## Answer No. It preserves the generated strings, but binarization adds administrative variables such as `BINARY`. To recover the original analysis, we must remove or collapse those nodes after parsing. ::: CNF gives the next algorithm its local combination rule: every nonterminal over a longer span must have been formed by one binary rule at one split point.