Confusion with first condition of Chomsky Normal Form

Question

I had a very quick question when it comes to CFG (more specifically the attributes of CNF). I've been browsing over some examples and I've come across a few that confuse me. One such example is this:

$$\begin{align}S&\to XA|BB\\ B&\to b|SB\\ X&\to b\\ A&\to a\\ \end{align}$$

It is stated that this is indeed in CNF, but my confusion lies in the fact that under most rules it is stated that if the starting state $S$ exists in some RHS (in this case $B\to b|SB$) we must create a rule that states $S'\to S$.

Since that doesn't exist in this example, why is this considered to be in CNF? I also understand the rules of CNF, I also see that this example technically satisfies all those rules, so I am wondering if that is the reason?

Rules: $$\begin{align}A&\to a\\ A&\to BC\\ \end{align}$$

Thank you for the help in advance!

Here is the link to the question for reference ( it deals with CFG TO GNF) https://www.geeksforgeeks.org/converting-context-free-grammar-greibach-normal-form/

Answer 1

Yes, your context-free grammar is in Chomsky Normal Form.

A grammar is in CNF whenever its rules are of one of two types, either $A\to BC$ or $A\to a$, where $A,B,C$ are nonterminals, and $a$ is a terminal symbol.

This means that every context-free grammar is equivalent to a cf grammar in CNF, up to the empty word. This means that by conversion into CNF one might loose the empty word. Nobody cares. Wikipedia refers to Hopcroft and Ullman as the source for CNF, and here is what H&U write:

Theorem 4.5 (Chomsky normal form, or CNF) Any context-free language without $\epsilon$ is generated by a grammar in which all productions are of the form $A\to BC$ or $A\to a$. Here, $A$, $B$, and $C$, are variables and $a$ is a terminal.

Except that some people with a wretched feeling for precision did not like this idea. They came up with a complicated formulation, just to capture the empty string. Probably something like "If the language contains $\epsilon$ then we allow the production $S\to \epsilon$, where $S$ is the axiom, and $S$ does not occur on the right-hand side of productions."

Well, your example grammar does not generate $\epsilon$ anyhow, so I would not bother. Chomsky didn't, Hopcroft and Ullman didn't. However, this is not legal advise. So, if someone is checking your exams, then I would consult that person.

Fun fact, Chomsky called "his" normal form "regular grammars"(!) and added a more restrictive condition: no two rules $A\to \alpha$ and $A\to \beta$ could share a common symbol in their right-hand sides $\alpha$ and $\beta$ (unless of course $\alpha =\beta$). (Definition 8, page 149, in the 1959 Chomsky paper linked at wikipedia).