1
$\begingroup$

I'm having trouble with this particular language: $$\{a^i b^j c^k \mid i+j \le k\}$$

If it's not context-free, I don't know how to correctly apply the Pumping Lemma for CFLs; if it is context-free, I don't know how to create a context-free grammar that generates this language.

Which one applies? Can you help me out?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Keep trying. Try both possibilities until one of them works. $\endgroup$
    – Yuval Filmus
    Dec 11, 2013 at 16:59
  • 3
    $\begingroup$ Suppose you had to generate such a string from the outside in (the first and last characters first, then the second and second-last, etc.) How might you do it? $\endgroup$
    – Niel de Beaudrap
    Dec 11, 2013 at 17:20
  • $\begingroup$ Awesome hint, Niel. It's clearer now. $\endgroup$
    – gbag
    Dec 11, 2013 at 18:29

2 Answers 2

Reset to default
2
$\begingroup$

Hint. $k = i + j + ?$, so the language is $a^ib^jc^?c^jc^i$.

Improve this answer
$\endgroup$
1
$\begingroup$

Here's a context-free grammar:

$$\begin{eqnarray} S & → & AC \\ AC & → & a \; AC \; c & \mid & BC \\ BC & → & b \; BC \; c & \mid & EC \\ EC & → & \varepsilon \; EC \; c & \mid & \varepsilon \end{eqnarray}$$

The $\varepsilon$ in the first RHS of $EC$ is of course not necessary, but it highlights a certain symmetry.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Bit confusing that AC is supposed to be a single non-terminal symbol. $\endgroup$
    – gnasher729
    Jun 12, 2019 at 21:26
  • $\begingroup$ I've added the adjective "context-free", from which one can infer that all the left-hand sides consist of a single non-terminals. One can then infer that some non-terminals' names consist of multiple letters. I tried renaming $S$ to $START$ to hit people on the nose with that fact, but it looks ugly (at least in the preview). $\endgroup$
    – Jonas Kölker
    Jun 24, 2019 at 11:19

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.