I was looking through my grammars book by Daniel I.A.Cohem "Introduction to Computer Theory". Chapter 16 goes into depth on Pushdown Automata Theory with Chomsky Normal Form.
Theorem 21
If L is a context-free language generated by a Context -free Grammar that includes A-productions, then there is a different context=free grammar that has no A-productions that generates either the whole language L or else generates the language of all the words in L that are not A.
If you never took grammars and after reading this were like what the..? A few pages later in the end of the proof, the author throws this great metaphor to help you understand the rules. I read it again and couldn't help laughing ...and enjoying:
Those never born need never die.
First statistician:
" With all the trouble in this world, it would be better if we were never born in the first place."
Second statistician:
"Yes, but how many are so lucky? Maybe one in ten thousand."
No comments:
Post a Comment