2
$\begingroup$

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.

$$L=\{a^{i_{1}}ba^{i_{2}}ba^{i_{3}}ba^{i_{4}}ba^{i_{5}}ba^{i_{6}}ba^{i_{7}}b|i_{1}>i_{2}>i_{3}>i_{4}>i_{5}>i_{6}>i_{7};i_{1}<100\}$$

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?

$\endgroup$
  • 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
5
$\begingroup$

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

$\endgroup$

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