1
$\begingroup$

I'm having problems in finding language of the CFG from given production rules. For example if the production rules are

\begin{align} &S \to AS \mid \epsilon \\ &A \to aa \mid ab \mid ba \mid bb \end{align}

How can I find the language it describes?

$\endgroup$
1
  • $\begingroup$ Could you share something you've tried, or perhaps some examples of strings in the language? $\endgroup$ – ADdV Oct 2 '20 at 15:58
2
$\begingroup$

The idiom "$X \to YX \mid \epsilon$" (or "$X \to XY \mid \epsilon$") 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.

$\endgroup$

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.