# Regular and context free languages

I need to determine if the following languages are regular / context free and to explain. Please help me with that.

$$L_1 = \{ a^{i_{1}}b a^{i_{2}}b a^{i_{3}}b a^{i_{4}}b a^{i_{5}}b a^{i_{6}}b a^{i_{7}}b a^{i_{8}}b a^{i_{9}}b a^{i_{10}}b \mid i_1 > i_2 > i_3 > i_4 > i_5 > i_6 > i_7 > i_8 > i_9 > i_{10} ; i_1 < 100 \}$$

$$L_2 = \{ a^{i_{1}}b a^{i_{2}}b a^{i_{3}}b a^{i_{4}}b a^{i_{5}}b a^{i_{6}}b a^{i_{7}}b a^{i_{8}}b a^{i_{9}}b a^{i_{10}}b \mid i_1 > i_2 > i_3 > i_4 > i_5 > i_6 > i_7 > i_8 > i_9 > i_{10} ; i_2 < 100 \}$$

$$L_3 = \{ a^{i_{1}}b a^{i_{2}}b a^{i_{3}}b a^{i_{4}}b a^{i_{5}}b a^{i_{6}}b a^{i_{7}}b a^{i_{8}}b a^{i_{9}}b a^{i_{10}}b \mid i_1 > i_2 > i_3 > i_4 > i_5 > i_6 > i_7 > i_8 > i_9 > i_{10} ; i_3 < 100 \}$$

• What are your own thoughts on the matter? Please use LaTeX to write your questions instead of using photographs of your exercise sheets. – Raphael Feb 16 '13 at 14:38

$L_1$ is finite. $L_2$ is a concatenation of $x^*$ and a finite language. $L_3$ is about a hard as $\{x^iy^j | i > j\}$. I'm leaving these as hints. Add a comment if you can't figure out why this is true.
• @user6885 $L_1$ is finite because all the $i$'s can take values less than 100 - so finite possible values. Hence the language has finite (but large) number of strings. Karolis never said $L_2$ is finite - he said it is a concatenation of $x^*$ to a finite language (making $L_2$ infinite). Try to figure out what is the finite part, and what is the $x^*$ part. – Paresh Feb 16 '13 at 16:24
• @user6885, the basic theory you should already know is that all finite languages are regular. Also, concatenation of two regular languages is regular. The last language in not regular (pump $a^{i_2}$). You'll have to figure out the grammar for it. The important thing is to realize that a long tail of every word is hardly relevant. The languages are really much simpler than they look. – Karolis Juodelė Feb 16 '13 at 17:19