1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – babou Apr 18 '15 at 19:58
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @HendrikJan You are right... I wanted to show how to use closure. Actually I first did it with $k$ using an erasing homomorphism. Then I thought a student might not know that, and I looked for intersection with a regular set, but the or had become an and in my mind ... hence the mistake. I am correcting. $\endgroup$ – babou Apr 19 '15 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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