Prove that $L$ is not a Context-free language, where $$L = \{ a^{i} b^{j}c^{h}\mid i,j,h\in \mathbb{N} \wedge h = \max(i,j)\}.$$

I have an idea: It can be divided into two situations:

  1. When $i < j$, $w = a^{i} b^{j} c^{i}$

  2. When $i > j$, $w = a^{i} b^{j} c^{j}$

Then with the help of the pumping lemma,but I will only use special examples to prove it. I always feel not rigorous. How should I write it more rigorously?

My writing is:

When $i < j$, $w = a^{i}b^{j} c^{i}$, $i = 4$, $j = 3$. $w = aaaa bbb cccc$, then use $uvxyz$ to prove step by step.

  • $\begingroup$ How should I write it more rigorously? Try to emulate known examples: ones that you've seen in class, ones that you've seen in textbooks, or ones that you've seen on Computer Science. $\endgroup$ Jul 13 '21 at 9:48
  • $\begingroup$ Just don't use specific values. For example, my process is to let i=4 and j=3. But I don’t think this is rigorous. $\endgroup$
    – 056040
    Jul 13 '21 at 10:07
  • $\begingroup$ providing a counter-example to a statement is rigorous $\endgroup$
    – Nikos M.
    Jul 13 '21 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.