TransWikia.com

How to find the language of a CFG from Production rules

Computer Science Asked by Stark2022 on February 3, 2021

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?

One 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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP