0
$\begingroup$

I am trying to prove why the below language is not context free. Note: this should be carried out by applying the pumping lemma for context free languages.

To prove something with the pumping lemma, we firstly need to choose an arbitrary m > 0. After that we need to formulate the string (alpha below) we are going to reach a contradiction with. But how do I formulate that string? Rational thinking lead me to believe it's the following:

What do I do next?
I have no idea about the length of $w$, and therefore the above approach seems kind of useless.

Is the solution to constrain $w$ to be of length at most $m$?
But again, I wouldn't know what to do from there.

Improve this question
$\endgroup$
3
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – Raphael ♦
    Aug 10, 2017 at 19:09
  • $\begingroup$ You may want to check out our reference question. Duplicate? $\endgroup$
    – Raphael ♦
    Aug 10, 2017 at 19:09
  • $\begingroup$ Note that you can include LaTeX directly into your posts by using $...$ and $$...$$. There's no need to link to third-party sites that render LaTeX as images. $\endgroup$
    – David Richerby
    Aug 11, 2017 at 9:30

1 Answer 1

Reset to default
1
$\begingroup$

Here in the notation of the language superscript $R$ is not a number; you cannot choose it to be a length $m$.

Instead $R$ usually denotes the operation of "mirror image" which inverts a string: $(abbaa)^R = aabba$.

Now start rereading your notes on the Pumping Lemma.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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