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?

  • 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.

| cite | improve this answer | |

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