I have eight textbooks on Formal Lang Theory on my desk. Six of them define a CFG to be in Chomsky Normal Form if every production is of the form either A-->BC or A--> σ (σ a single letter). With that definition one can show that every e-free grammar can be put in Chomsky Normal Form, and using that, show that CFL ⊆ P. There is a very minor issue of what to do if the CFL has e in it.
Two of the books (Sipers and Floyd-Beigel) define a CFG to be in Chomsky Normal Form if every rule is A-->BC or A--> σ OR S-->e and also that S cannot appear as one of the two nonterminals at the right hand side of a production of the form A-->BC. With this definition you can get that every CFL (even those with e in them) has a grammar in Chomsky Normal Form.
The definitions are NOT equivalent mathematically, but they are equivalent in spirit and both aim towards the same thing: getting all CFL's in P (That's why I use them for. What did Chomsky used them for?)
The first definition is correct historically- its what Chomsky used (I am assuming this since it's in the earlier books). The second one could be argued to be better since when you are done you don't have to deal with the e. I still like the first one, but its six of one, half a dozen of the other. One person's floor function is another person's ceiling function.
I don't have a strong opinion about any of this, but I will say that if you use the second definition then you should at least note that there is another definition that is used for the same purpose. Perhaps make a homework out of this.
There are many other cases where definitions change and the new one leads to more elegant theorems and a better viewpoint than the old one. There are even cases where the new definition IS equivalent to the old one but is better. IMHO the (∃) definition of NP is better than the definition that uses nondeterministic Poly Time TM's since this leads to the definition of the poly hierarchy. One drawback- if you want to define NL then I think you DO need nondeterministic TM's.
The only problem I see with changing definitions is if you are reading an old paper and don't quite know which definition they are using.
What examples of a definition changing (or an equivalent one being more used) do you approve of? Disapprove of?
Non-deterministic time has several definitions, whether we want only one accepting run to be at most $f(n)$, or all possibles runs to be at most $f(n)$. This makes no difference if $f$ is some nicely computable function, but for other $f$ can be a problem.
ReplyDeleteAnother definition where one has to be very careful is sublinear space complexity.
LOGCFL as LOG-space reducible to CFL recognition vs languages computable by uniform semi-unbounded fan-in circuits of O(log n) depth.
ReplyDeleteThe latter seems preferable mostly because it makes the class seem more natural.
You can use quantification with logarithmic space, if you give the witness string only as one-way input.
ReplyDelete