Can the following CFG be converted to a Regex ?
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").