1
$\begingroup$

Is anybody can help me please to determine is this language is Context-free language or not?

L={wvw | w,v∈{a,b,c}+}

for example:

part of the language: acbac, abcab, bbcbb

not part of the language: abab, aa, abcc

I tried to prove using pumping lemma for context-free languages like that:

I take this word from language w=aacbbaa. I split the word to 5 parts uvxyz and if I can pump u and y and the word stays inside language the language is context-free:

u-aa, v-cc, x-b, y=bb, z=aa 
after I pump v and y the word is still in language-> 
u-aa, v-cccc, x-b, y=bbbb, z=aa -> 
aaccccbbbbbaa

But the answer inside answers section is that the language is not context-free.

What wrong with my prof?

$\endgroup$
  • 1
    $\begingroup$ Same language here: "Is {xyx | |x|≥1} context-free?" cs.stackexchange.com/q/11629/4287, where one of the answers suggests the pumping lemma can be used to show the language is not context-free. $\endgroup$ – Hendrik Jan Mar 8 at 22:48
2
$\begingroup$

You can't use the pumping lemma to prove that a language is context-free (see, e.g., here). The pumping lemma is only useful to prove that the language is not context-free. See our reference questions for details on how to prove that a language is or isn't context-free: How to prove that a language is context-free?, How to prove that a language is not context-free?.

So, one thing wrong with your proof is where you say "if... the word stays inside language the language is context-free" -- that's not correct.

$\endgroup$
  • $\begingroup$ D.W. , thanks for post.If pumping lemma not works for any part(y and u) in word I can say that langauge is not context free? $\endgroup$ – Michael Mar 8 at 19:30
  • 1
    $\begingroup$ @Michael, sorry, this site isn't designed for back-and-forth interactive assistance. I encourage you to study our reference material, and if you need more interactive help, perhaps you can find a friend, tutor, or teaching assistant to help you. $\endgroup$ – D.W. Mar 8 at 19:31
  • $\begingroup$ D.W. only one question is this language is context free or not? $\endgroup$ – Michael Mar 8 at 20:30

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.