-1
$\begingroup$

This question already has an answer here:

How can one prove that the language below is not context-free using the pumping lemma?

$$\{ a^i b^m a^j b^m a^k b^m \mid i,j,k,m \geq 0 \}$$

$\endgroup$

marked as duplicate by Yuval Filmus, Raphael May 15 '17 at 22:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You cannot, since this language is context-free. $\endgroup$ – Yuval Filmus May 15 '17 at 18:51
  • $\begingroup$ can explain more for your answer ? @YuvalFilmus $\endgroup$ – shahin gh May 15 '17 at 18:56
  • $\begingroup$ can you build a PDA/define a CFG for $b^mb^m$? If so, you can do it also for $a^*b^ma^*b^ma^*$. $\endgroup$ – abc May 15 '17 at 19:05
  • $\begingroup$ sorry , i edited the language , so you said there is no possible way to prove ? @newbie $\endgroup$ – shahin gh May 15 '17 at 19:20
  • 1
    $\begingroup$ The point of exercises such as this is to give you practice in using the pumping lemma. Whatever learning resource you're using (textbook, lecture notes, etc) probably already has several examples of using the pumping lemma. Us turning this exercises into another example for you probably won't help you a whole lot: the benefit comes from figuring it out yourself. $\endgroup$ – David Richerby May 15 '17 at 22:12
-1
$\begingroup$

Suppose that $a^* b^m a^* b^m a^* b^m$ is context-free. Applying the inverse of the homomorphism defined by $a\mapsto a$ and $b,c,d \mapsto b$, we see that $a^* (b+c+d)^m a^* (b+c+d)^m a^* (b+c+d)^m$ is also context-free. Intersecting with the regular language $b^* a c^* a d^*$, we see that $b^m a c^m a d^m$ is also context-free. Applying the homomorphism defined by $a \mapsto \epsilon$ and $\sigma \mapsto \sigma$ for $\sigma=b,c,d$, we see that $b^mc^md^m$ is also context-free. But we know that it's not context-free.

$\endgroup$
  • $\begingroup$ "using the pumping lemma" $\endgroup$ – David Richerby May 15 '17 at 22:09
  • $\begingroup$ Thanks but we can not change the alphabet into three other alphabet! $\endgroup$ – shahin gh May 16 '17 at 7:01
  • $\begingroup$ @DavidRicherby I am using the pumping lemma to prove that $b^mc^md^m$ is not context-free... :) $\endgroup$ – Yuval Filmus May 16 '17 at 7:02
  • $\begingroup$ @shahingh Who said we cannot do that? In mathematics, we have the complete freedom to do anything which is mathematically valid. $\endgroup$ – Yuval Filmus May 16 '17 at 7:02

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