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?

|cite|improve this question|||||
$\endgroup$
  • 2
    $\begingroup$ Keep trying. Try both possibilities until one of them works. $\endgroup$ – Yuval Filmus Dec 11 '13 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 '13 at 17:20
  • $\begingroup$ Awesome hint, Niel. It's clearer now. $\endgroup$ – gbag Dec 11 '13 at 18:29
2
$\begingroup$

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

|cite|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.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ Bit confusing that AC is supposed to be a single non-terminal symbol. $\endgroup$ – gnasher729 Jun 12 '19 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 '19 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.