This question already has an answer here:

I am struggling with a homework assignment. This next question seems to be pretty easy, once I get what I feel like I'm missing now. Anyway, here goes:

Decide if the following language is regular or not and prove your claim.


So, how do I go about doing so? Is there a thumb rule that might help? I was trying to use the pumping lemma to prove that it is not regular, but couldn't do it. I'm not even sure it really is not regular.

Any suggestions?


marked as duplicate by Paresh, vonbrand, Raphael Mar 17 '13 at 18:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from cstheory.stackexchange.com Mar 16 '13 at 18:45

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ This wouldn't happen to be HUJI homework, would it? Try asking your TAs. I heard they are really helpful :) Also, this question fits cs.se, not tcs.se. $\endgroup$ – Shaull Mar 16 '13 at 18:16
  • $\begingroup$ I remember seeing this exact same question, with two more related questions, but can't seem to find it, probably because that question had a picture of the question. $\endgroup$ – Paresh Mar 16 '13 at 19:56
  • $\begingroup$ @Paresh - this is the post with this question, which was indeed the basis for the OP's post (the other two questions also appear in the OP's homework...) $\endgroup$ – Shaull Mar 16 '13 at 20:12
  • $\begingroup$ @Shaull Although I think this question is a much better post, we should mark it as a duplicate of the other question. $\endgroup$ – Paresh Mar 17 '13 at 14:12

Hint: Consider how many words are in $L$. The answer will then be immediate.


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