关于乔姆斯基范式（CNF）文法移除左递归、左因子后是否保留范式形式的技术问询

Great questions! Let's start with a quick recap of Chomsky Normal Form (CNF) rules to set the stage: every production must be either A → BC (two non-terminals) or A → a (a single terminal). The only exception is the start symbol, which can optionally have a S → ε production—all other non-terminals can't produce empty strings.

Now let's break down your questions one by one:

1. Does a CNF grammar remain in CNF after both eliminating left recursion and left-factoring? #

Short answer: No. Both operations introduce structures that violate CNF rules, and combining them makes this even clearer.

For example, take a simple CNF grammar with immediate left recursion:

A → AA | a

Eliminating left recursion gives us:

A → aA'
A' → AA' | ε

The A' → ε production is a problem—CNF doesn't allow non-start symbols to produce empty strings. If we then add left-factoring to a more complex case, like:

A → AB | AC | a

Left-factoring would first rewrite this to A → A(B|C) | a, which uses grouped alternatives (the (B|C) part)—a structure that's not allowed in CNF. Even if we split that into auxiliary productions, combining with left recursion elimination would still leave us with ε-productions or productions that don't fit the strict two-non-terminals-or-one-terminal rule.

2. Does a CNF grammar stay in CNF if we only eliminate left recursion, or only left-factor? #

Neither operation preserves CNF—let's explain each case:

Only eliminating left recursion #

Eliminating left recursion (whether immediate or indirect) requires introducing auxiliary non-terminals, and those auxiliaries almost always get an ε-production. As we saw in the first example, A' → ε breaks CNF because only the start symbol can have an empty production. Even for indirect left recursion, substituting productions to expose the recursion leads to longer right-hand sides, and fixing those while eliminating recursion still results in non-CNF structures like the ε-productions.

Only left-factoring #

Left-factoring creates productions that don't fit CNF's strict form. Let's take an example:

A → aB | aC

Left-factoring this gives us:

A → aA'
A' → B | C

The problem here is A' → B and A' → C—these productions have a single non-terminal on the right-hand side, which isn't allowed in CNF. CNF requires right-hand sides to be either two non-terminals or one terminal, not a single non-terminal. Even if you try to adjust this, you can't make it fit CNF without altering the grammar in ways that defeat the purpose of left-factoring.

内容的提问来源于stack exchange，提问作者Ron Turetzky