Are these languages regular?

28 Views Asked by At

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

1

There are 1 best solutions below

2
On

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.