fixed point in regular expressions

Question

I've posted this question first on StackOverflow but this section seems more suited for this kind of questions. Also I'm not trying to simply solve this exercise (it is a "parsing" exercise, once I'll figure out the regular expression I'll derive the equivalent Finite Automaton that accepts the language generated by the grammar), but instead I'm trying to understand the methodology to derive regular expressions (if they exists, from context-free grammars)

I have this productions of a context free grammar (axiom S, e is the empty word)

S->AS|b|A A->abA|Ab|e I have to figure out a regular expression (if exists) that generates a language equivalent to the one generated by that grammar.

So far i wrote that

L(S)=L(A)L(S) + b + L(A) = L(A)*(L(A) + b) (by Arden Rule)
L(A)=(ab)*(L(A)b+e)

I've tried the method of finding the fixed point (I'd like more info about that since seems I can't get the hang of it

for A: 0 -> e -> (ab)*(b+e) -> (ab)*[(ab)*(b+e)](b+e)

should i check if (ab)(b+e) = (ab)(ab)*(b+e) (if that's is the fixed point? Or should i go ahead?) It's not the first exercise I'm having trouble with so any help would be appreaciated, Thanks.

Answer 1

As all productions in $A\rightarrow \mathrm{ab}A\text{ }|\text{ }A\mathrm{b}\text{ }|\text{ }ε$ are linear, and (crucially) there is only one non-terminal symbol, all derivation sequences can be reordered into equivalent ones where left-side derivations always precede (or always succeed) right-side ones.

For instance:

$wAv \Rightarrow w\mathrm{ab}Av \Rightarrow w\mathrm{ab}A\mathrm{b}v \Rightarrow w\mathrm{abab}A\mathrm{b}v \Rightarrow w\mathrm{abab}A\mathrm{bb}v\equiv \\wAv \Rightarrow wA\mathrm{b}v \Rightarrow wA\mathrm{bb}v \Rightarrow w\mathrm{ab}A\mathrm{bb}v \Rightarrow w\mathrm{abab}A\mathrm{bb}v$

(This is a hint of what an inductive proof using fixed-points would look like in this particular case. Check this if you are determined to go down that road).

This means that this grammar can be converted into a regular grammar in two steps, by grouping left-linear and right-linear productions:

1.

$A \rightarrow A'A''\\A' \rightarrow \mathrm{ab}A'\text{ }|\text{ }ε$
$A'' \rightarrow A''\mathrm{b}\text{ }|\text{ }ε$

2.

$A \rightarrow A'A''\\A' \rightarrow \mathrm{ab}A'\text{ }|\text{ }ε$
$A'' \rightarrow \mathrm{b}A''\text{ }|\text{ }ε\\$

So $\mathcal{L}(A) = (\mathrm{ab})^*\mathrm{b}^*$