What does this CFG accept?

Question

I am not sure what this language accepts:

$S \to 01S2A\,|\,\epsilon$

$A \to 1A\,|\,1$

I thought something like: $(01)^i(21)^i1^n$ But then I didn't know how to handle all the 1's that can come after each 2.

Answer 1

Suppose that you apply the production $S\to 01S2A$ $m$ times before applying $S\to\epsilon$; the result is $(01)^m(2A)^m$. Each $A$ then generates a string of one or more $1$s, so you end up with

$$(01)^m21^{n_1}21^{n_2}\ldots 21^{n_m}\;,$$

where $n_1,\ldots,n_m$ are positive integers. Note that $m$ can be $0$, in which case you get the empty word.

In short, you get the empty word, and every word that starts with some positive number $m$ of copies of $01$, followed by $m$ strings of the form $21^+$. We can write the general form as $(01)^m(21^+)m$, where $m\ge 0$.