I am reading a fabulous book on Formal Languages and in the book it says:
As the rewrite rules of a grammar become more complex, the algorithm for recognizing the associated language becomes more involved.
The book shows the rewrite rules for this language:
The rewrite rules -- the grammar -- is complex. But it seems to me that the algorithm for recognizing whether a string is a member of that language is trivial:
(count(a) == count(b)) and (count(a) == (count(c))
Doesn't that contradict the book's statement?
Let me take a stab at answering my own question. I'd appreciate your thoughts on whether my answer is on the right track.
My answer: The
count() function is hiding a huge amount of complexity. The underlying code that implements the
count() function requires an enormous amount of computational power: probably a tape (i.e., memory), the ability to move left and right on the tape, and lots of complex transition rules. Contrast with, say, a regular grammar where the computational power required is far less: in fact, no memory is required. With a regular grammar we could recognize strings using a simple machine. Unfortunately today everything is run on these high-powered desktop computing machines and we have no idea that under-the-hood regular grammars use far less computing resources than, say, the grammar for anbncn.
Is my answer close? Am I on the right track? What would you add to my answer?