1
$\begingroup$

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$, then which of the following statements are true?

  1. $L_1\cup L_2$ is a context free language
  2. $L_1\cap L_2$ is a context free language
  3. $L_1- L_2$ is not regular
  4. $L_1$ and $L_2$ both are regular languages

My attempt:

Since, language $L_1=\{a^pb^qc^r|p,q,r>0\}$ is regular and $L_2=\{a^pb^qc^r|p,q,r\geq0 \space\text{and}\space p=r\}$ is context free but not regular.

So, here

Statement $(1)$ $L_1\cup L_2=\{a^pb^qc^r|p,q,r \geq0\}$ is regular, so also context free language, statement is true.

Statement $(2)$ $L_1\cap L_2=\{a^pb^qc^r|p,q,r>0 \space\text{and}\space p=r\}$ is context free but not regular, statement is true.

Statement $(4)$ is obviously false as $L_2$ is not regular language.

I'm stuck at statement $(3)$ $L_1- L_2=L_1\cap \overline{L_2}$ it should be context free but not regular language?

Can you explain in formal way, please?

$\endgroup$
1
$\begingroup$

Let $L = L_1 - L_2 = \{a^pb^qc^r \mid p,q,r > 0, p \not=r\}$ and suppose that $L$ is regular. Then the language $a^+bc^+ - L = \{a^pbc^p \mid p > 0\}$ would also be regular, which is not the case. Thus $L$ is not regular.

$\endgroup$

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.