I agree with you and Raphael that the first question should not have been closed as "too basic", and I think Raphael has provided a perfectly reasonable explanation and response. Hey, we're all human.
That said, the first question has other.. blemishes and could be improved. One problem is that the question doesn't give any indication of why the author thinks that "we can test for regularity using the Myhill–Nerode theorem". This is a sign that the author hasn't put in as much effort as he/she could have (he/she should have tried working out the details, and then maybe he/she would have figured out the answer for himself/herself), and it also forces answerers to try to guess what might have been in the author's mind.
In general, when you see a question that you think should not have been closed, here are some constructive things you can do:
Editing the question to improve the question to address any comments it has gotten and any plausible, anticipable misunderstandings and to make it more useful to others.
Cast a re-open vote.
Post here to ask others to cast re-open votes.
If it was closed by a moderator and you think that was in error, flag it for moderator attention.
Obviously, you've done the third. Obviously, everything worked out fine in the end. Just mentioning other constructive actions one can take, for others who may be reading this, in case they find it helpful in the future. In particular, I encourage you to consider editing questions to improve them, if you see a question that you don't think should have been closed. That can be very helpful.
All in all, I'm not persuaded we treat people too harshly. Very occasionally we make a mistake, but generally the process seems to be self-correcting, and I think we get it right the overwhelming majority of the time. And hey, no process will ever be perfect. So I don't think we have a major problem; I think we get the balance about right. Just my opinion.