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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Could you share something you've tried, or perhaps some examples of strings in the language? $\endgroup$– ADdVOct 2, 2020 at 15:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Oct 2, 2020 at 18:34