Talk:Chomsky normal form
From Wikipedia, the free encyclopedia
 |
This article is within the scope of the WikiProject Philosophy, which collaborates on articles related to philosophy. To participate, you can edit this article or visit the project page for more details. | ||||||||
| ??? | This article has not yet received a rating on the quality scale. | ||||||||
| ??? | This article has not yet received an importance rating on the importance scale. | ||||||||
|
|||||||||
[edit] 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)
