Prove if $\{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$ is regular or not

Question

$$L = \{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$$

To Prove: If given language is regular or not.

I know that it is not a regular language but I am not able to come up with the string which I can use in the pumping lemma to prove that it is not regular.

We can also divide $L$ into two parts: $$\begin{align*} L_1 &= \{x^iy^jz^k \mid i \le 2j\}\\ L_2 &= \{x^iy^jz^k \mid j \le 3k\}\,, \end{align*}$$

so I just need the strings to be used in the pumping lemma for $L_1$ and $L_2$.

Answer 1

It's not regular. Hint: Let $p$ be the integer of the pumping lemma and pump the string $x^{6p}y^{3p}z^{2p}$.

Answer 2

Decomposing the language $L$ into union or intersection of two simpler languages is useful to prove that L is regular, but it will not help you (in general) to prove that $L$ is not regular. The union or intersection of two non regular languages can be regular.

However, you can use these closure properties differently, to eliminate $x$. Consider the language $R=x^*y^*$. This language is regular. Its intersection with $L$ is $L'=L\cap R=\{x^iy^j \mid i \le 2j\}$ keeping only the words were $z$ has exponent $0$.
This is because $L_2\cap R=\{\epsilon\}$. So $L'=L\cap R=(L_1\cup L_2)\cap R=(L_1\cap R)\cup(L_2\cap R)=(L_1\cap R)\cup\{\epsilon\}=L_1\cap R$ because $\epsilon\in L_1\cap R$.

If $L$ were regular, then $L'$ would also be regular because $R$ is regular, and the intersection of regular languages is regular.

Thus if you can prove that $L'=\{x^iy^j \mid i\le 2j\}$ is not regular, you can infer that $L$ is not regular.

And you should be able to prove it for $L'$.

There are other ways of using closure properties to simplify the language. For example you could use an erasing homomorphisn to replace all $z$ by the empty word, which would lead you to the same language $L'$, And regular languages are closed under arbitrary homomorphism.

Closure properties can be very friendly, if you learn to use them. Then can considerably simplify some problems. See How to prove that a language is not regular?

With thanks to Hendrik Jan for catching a shameful bug.