My initial thought is that L can't be context free since I can use the pumping lemma. I also don't think a grammar can be generated since it needs to keep track of the number of c's and a's. However, I'm having a hard time coming up with an algorithm for this language.


Here's a hint:

  1. Could you make a grammar for $a^nb^n$, $n\ge 0$?
  2. Could you make a grammar for $b^mc^m$, $m\ge 0$?
  3. Could you make a production that concatenates the languages in (1) and (2) above?

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.