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, 2020 at 15:58

1 Answer 1

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 and acknowledge you have read our privacy policy.

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