How to find the language of a CFG from Production rules I'm having problems in finding language of the CFG from given production rules. For example if the production rules are
\begin{align}
&amp;S \to AS \mid \epsilon \\
&amp;A \to aa \mid ab \mid ba \mid bb 
\end{align}
How can I find the language it describes?
The idiom &quot;$X \to YX \mid \epsilon$&quot; (or &quot;$X \to XY \mid \epsilon$&quot;) means that $X$ generates $Y^*$ (assuming there are no other productions for $X$). This means that your grammar generates $A^*$. You know what $A$ generates. Putting everything together, you should be able to find a very concise description of the language generated by your grammar.