4
$\begingroup$

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:

anbncn

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?

$\endgroup$
  • $\begingroup$ The pigeonhole principle. There aren't very many simple algorithms and there are a lot of complicated grammars. $\endgroup$ – Qiaochu Yuan Aug 3 '13 at 1:56
2
$\begingroup$

The comment was to short, so I'm posting this as an answer.


Theoretical complexity is different than practical complexity.

Theoretically, your computer can recognize only finite language, so its strength of expression is even smaller that regular languages. What matters here is memory, i.e. space. Your computer has finite memory, you need to assume that we can build arbitrarily large computers, and then you could, theoretically, parse any regular language.

count(.) isn't complex, but it needs memory, possibly infinite memory. Imagine that two (independent) counters is enough to simulate Turing machine.

As to answer your first question, the problem isn't to recognize one simple language like $a^nb^nc^n$, the challenge is to parse any language that the grammar makes possible, and that might include (depending on the grammar) things much more complex than just counting. Whenever you make grammar more powerful, there's often a whole new range of possibilities that the algorithm needs to take into account, and that makes it more and more involved, exactly as the book says.

I hope this helps $\ddot\smile$

Edit: To avoid confusion: computer's memory is finite, so in its memory it can recognize only finite languages. However, if you would pass an external input to the computer (like signal processing), then, if you would find a way around technical limitations (continuous power supply, etc.), then it could recognize some infinite languages (arbitrarily long finite strings are enough for a language to be infinite), i.e. those that doesn't require more states than its memory.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.