How to find the language of a CFG from Production rules

Question

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?

Yuval Filmus · Answer

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 by Yuval Filmus on February 3, 2021

How to find the language of a CFG from Production rules

One Answer

Add your own answers!

Ask a Question