CODEWITHSUNDEEP
regexexpresscontext-free-grammar
Marcus F
Marcus F

Reputation: 535

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

Upvotes: 0

Views: 118

Answers (1)

rici
rici

Reputation: 241911

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").

Upvotes: 2

Related Questions