[Fixed] Regex and grammar free context conversion


Can the following CFG be converted to a Regex ?

enter image description here

Someone said that this could be it regex: (ab* a + b)*

is this true and why? I cant seem to understand it


It’s not a regular language.

Consider the subset of the language with exactly one b. (In other words, the intersection of the language with a*ba*.) If the language were regular, that subset would also be regular, since it would be the intersection of two regular languages.

But it’s not regular, since it consists of strings in which the number of as following the b is at least as large as the number of as preceding the b, and that is not a regular language ("regular languages can’t count").

Leave a Reply

(*) Required, Your email will not be published