1. 3
  1.  

  2. 1

    Well, as far as I know, the Myhill–Nerode theorem itself isn’t actually very important.

    This isn’t the main point of the post, but I’d quibble with this part. The theorem is useful for proving languages regular or (perhaps more often) nonregular, by showing that a given language has a finite or infinite set of equivalence classes distinguished by extensions. I suppose how important that is could be argued too, but it’s sometimes useful to know whether a particular language is regular, and this is a tool for doing so.

    Or is this referring only to the minimal automaton construction? As far as I understand it, that’s usually taken to be an implication of the theorem but not “the” theorem.

    1. 1

      The theorem is useful for proving languages regular or (perhaps more often) nonregular

      I mean, I’ll grant that’s a useful thing to do, and I’ve heard this before (OK, I’ve read it on the wikipedia page), but do you have an actual example of a language which it’s easier to do this with than it is to do it with the pumping lemma (which seems to be the more common approach and more easily mechanically applied)?

      Or is this referring only to the minimal automaton construction? As far as I understand it, that’s usually taken to be an implication of the theorem but not “the” theorem.

      Yeah, the automaton isn’t normally really the point of the theorem, but it’s useful in its own right for reasons that become apparent in the next two posts in the series (today’s and tomorrow’s).