At first I thought the language would be context sensitive because it seems that it can be shown with the pumping lemma for regular languages, that it's not a regular language and analogously with the pumping lemma for context free languages, that it is not context free. But it upon further pondering I came up with a pushdown automaton that would match this language. So I'm a bit at loss as to what type of language it is. I hope someone can help.

  • 4
    $\begingroup$ I'm not sure what you mean by "it seems that it can be shown". Do you mean that you have written down what you believe to be a proof, or just that you feel that a proof should exist. If the latter, I suggest you try to write down the proofs and see where that gets you. As I'm sure you know, if there's a PDA for the langauge, it's context-free so either your automaton is wrong, your context-free pumping lemma proof is wrong or your suspicion that there exists such a proof is wrong. If all you have is a suspicion, you should definitely try to produce an actual proof. $\endgroup$ – David Richerby May 23 '16 at 20:02

The language is context-free. You can use the pumping lemma for regular languages to show that it is not regular. However, you can construct a context-free grammar to show that the language is context free. For example, the following CFG grammar would generate it

$S \to A\ |\ aS $

$A \to \epsilon\ |b A cc $

| cite | improve this answer | |

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.