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.