2
$\begingroup$

Consider the language generated by the following grammar:

$S \to aSBb \mid \epsilon$

$B \to aB \mid bB \mid \epsilon$

Is the above language context-free?


The above language looks like $\{ w \in (a+b)^* : a^n w_1b w_2b ... w_nb \}$.

I tried using the pumping lemma to show that this language is not context-free, but I was unable to do so.

$\endgroup$
6
$\begingroup$

Hint: A language $L$ is context-free iff there exists a context-free grammar $G$ such that $L = L(G)$. (Some people take this as the definition of context-free languages.)

$\endgroup$
  • $\begingroup$ Damn, I didn't see that the grammar itself is CFG and was trying to construct a PDA. But the language is not DCFL right ? $\endgroup$ – Zephyr Jan 7 '18 at 12:16
  • 2
    $\begingroup$ That's a different question. $\endgroup$ – Yuval Filmus Jan 7 '18 at 12:26

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.