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.
$\begingroup$
$\endgroup$
1
-
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 RicherbyMay 23, 2016 at 20:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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 $
-
1
$\begingroup$
$\endgroup$
1
If the language required twice as many c's as a's, the equivalent grammar should look like
S -> aScc | bB | epsilon
B -> bB | epsilon
-
$\begingroup$ (Have another look at the specification of $L$?) $\endgroup$ Mar 31, 2023 at 8:11