0
$\begingroup$

I have a problem where I am asked to explain why the language that has words made of $a$ and $b$ such that the number of $a$'s is equal to the number of $b$'s, can be generated by a context free grammar. I am not sure of what is asked here, will finding such a grammar work? What should I do?

$\endgroup$
0
$\begingroup$

Usually, to prove that some language is a CFL (which is equal as asking whether it is generated by some CFG) you can show:

  1. It is generated by some CFG. Proving is usually done by induction, where one direction is an induction on the number of derivation steps, and the other direction is usually an induction on the length of the word.
  2. Showing a PDA that accepts the language.
  3. Using closure properties of CFL, and generate the language from some finite number of CFL/regular languages using closure properties (like concatenation, union, etc..)
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Welcome, and thanks for taking the time to answer! You may want to make yourself familiar with our list of reference questions which we have assembled to avoid having to answer the same questions over and over again. See you around! $\endgroup$ – Raphael Jan 23 '18 at 11:53

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