Talk:Chomsky normal form

This article is within the scope of WikiProject Philosophy, a collaborative effort to improve the coverage of content related to philosophy on Wikipedia. If you would like to support the project, please visit the project page, where you can get more details on how you can help, and where you can join the general discussion about philosophy content on Wikipedia.PhilosophyWikipedia:WikiProject PhilosophyTemplate:WikiProject PhilosophyPhilosophy

???

This article has not yet received a rating on Wikipedia's content assessment scale.

???

This article has not yet received a rating on the project's importance scale.

Associated task forces:
/
	Logic

Following Sipser's Lead

I see that the original article follows Sipser pretty closely, including allowing epsilon to be in the language. As far as I know, this is in fact a little EXTENSION to the original idea of CNF. Here is how Hopcroft, Motwani, and Ullman define CNF:

"all productions [in the grammar] are in one of two simple forms, either:

1. A --> B C, where A, B, and C are each variables, or 2. A --> a, where A is a variable and a is a terminal.

Further, [the grammar] has no useless symbols."

Note the differences from the Sipser presentation: no epsilon rule at all, no restrictions on B and C except that they are variables.

By this (H/M/U's) definition, you can create a CFG in CNF for any CFL that does not include epsilon. If the CFL includes epsilon, you are out of luck. I speculate this is the original definition. Sipser also omits the mention of useless symbols.

Question: Is my speculation correct?

Question: If so, does the 'original' definition of CNF deserve a mention?

Question: Who developed this extension that Dr. Sipser presents? Was it he himself?

Also I've edited the article to add that (in the extended version) the start variable is not allowed to be on the right side of any production (a necessary wrinkle since we allow the epsilon rule for this variable).

LandruBek 07:14, 22 March 2006 (UTC)[reply]

How is it different from the Backus Naur/Normal Form?

I am guessing it's the same. Can someone confirm/refute this? I think the relation to BNF should be mentioned in the main article. SDX2000 (talk) 15:43, 26 May 2009 (UTC)[reply]