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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.)

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jan 7, 2018 at 12:16
  • 2
    $\begingroup$ That's a different question. $\endgroup$
    – Yuval Filmus
    Commented Jan 7, 2018 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.