2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Also posted on Stack Overflow. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. $\endgroup$ – D.W. Jul 6 '15 at 3:01
  • $\begingroup$ I've deleded the post in StackOverflow, this section seems more appropriate $\endgroup$ – Crysis85 Jul 6 '15 at 9:35
3
$\begingroup$

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}^*$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.