Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 \}$$

share|improve this question
3  
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

1 Answer 1

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

share|improve this answer
    
why L1 & L2 is finite? –  user6885 Feb 16 '13 at 13:51
    
@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
    
Maybe i1? but what this is say to me on a free content language? –  user6885 Feb 16 '13 at 16:35
    
@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
    
ok ,what i still dont understand is L2 .if i concatenation between ai1b and ai2...ai10b so its became regular ? –  user6885 Feb 16 '13 at 17:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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