0
$\begingroup$

I am trying to deduct how i can, using closure properties, deduct that since the following language is not context free $$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$$

Such that:

$m,n,o \geq 1;$

$m>n>o>0;$

$i_1,i_2,...,i_{2m} \geq 0;$

$j_1,j_2,...,j_{2n} \geq 0;$

$k_1,k_2,...,k_o \geq 0$

this language is also: $$L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$$

My attempt: basically, they both look very similar, but I am not sure the coming procedure is correct: If we take $L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$, Unionize bc, ef and hq to obtain the following: $L=\left\{aB^{i_{2m}^*}dE^{j_{2n}^*}gH^{k_o^*}\right\}$, And then using assignment or homomorphism, defining $h:B^{i_{2m}^*} -> 0^{i_{2m}^*}$, $h:E^{i_{2n}^*} -> 1^{j_{2n}^*}$ , $h:H^{k_o^*} -> 2^{k^*_o}$ obtaining: $L=\left\{a0^{i_{2m}^*}d1^{j_{2n}^*}g2^{k^*_o}\right\}$. Since we can decompose string S using the pumping lemma into $S=uvxyz$ as we choose, We can only regard the $0^{i_{2m}^*}1^{j_{2n}^*}2^{k^*_o}$ part. Because of that, And knowing in advance that $L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$ is not context free, we can deduct that $L=\left\{a0^{i^*_{2m}}d1^{j^*_{2n}}g2^{k^*_o}\right\}$ is not context free as well.

Would really appreciate your corrections or knowing if there exists a better and easier way to deduct that.

Thank you very much.

$\endgroup$
3
  • $\begingroup$ It is not a possible duplicate, because i asked different things here. $\endgroup$
    – Auto
    Jun 28, 2019 at 11:41
  • $\begingroup$ Checking people's work is off-topic, because it's only ever interesting to the person who did the work. We prefer to spend our time on questions that will be useful to other people in the future. As for "is there a better and easier way?" your proof is already only a paragraph long: you're not going to get anything shorter than that for a language whose definition is so long and messy. $\endgroup$ Jun 28, 2019 at 13:56
  • $\begingroup$ So please close the thread then. I already got an answer in other thread, and I cannot delete it out of respect to the persons who commented here and gave me a short explanation in the answer section. $\endgroup$
    – Auto
    Jun 28, 2019 at 14:00

1 Answer 1

1
$\begingroup$

If I understand your argument correctly, you are reducing languages in the wrong direction.

If $L$ is not context-free, then $K$ is not context-free.

Is equivalent to

If $K$ is context-free, then $L$ is context-free.

We have to reverse the construction, as we are using the closure properties of the context-free languages. In do not know of any useful closure properties of the non-context-free languages.

PS. The pumping argument seems out of place here.

$\endgroup$

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