1

$L_1 = \{0^k1^n \mid k \equiv n \bmod 3 \}$

This one I assume isn't since it's infinite

$L_2 = \{0^k1^{3k+2} \mid k>0 \}$

This one I assume also isn't regular because it relates on $k$ on both $0$ and $1$, and we can't store the amount of $0$'s we had so far

Am I right? Sorry if I'm mistaken, I'm new in the subject. And how do I prove these to be right/wrong?

J.-E. Pin
  • 40,163
miyumiyu
  • 21

1 Answers1

1

Hint. The language $L_1$ is regular. To show this, observe that $$L_1 = \{0^{3k}1^{3n} \mid k, n \geqslant 0 \} \cup \{0^{3k+1}1^{3n+1} \mid k, n \geqslant 0 \} \cup \{0^{3k+2}1^{3n+2} \mid k, n \geqslant 0 \}$$ For the second question, use the pumping lemma to show that $L_2$ is not regular.

J.-E. Pin
  • 40,163
  • But the thing is that k is equal to n, so it's like saying basically.. 0^n1^n, is it not? – miyumiyu Nov 15 '18 at 16:19
  • You mean for $L_2$? Yes, this is the same kind of proof. If you already know that ${0^n1^n \mid n \geqslant 0}$ is not regular, you could actually use this fact to prove that $L_2$ is not regular without using the pumping lemma. – J.-E. Pin Nov 15 '18 at 18:01