Let say we have the following grammar G:
S -> bA
-> aB
-> 1
A -> aA
-> bB
B -> bA
-> aB
-> 1
How would i go about solving the corresponding semiring equations to derive a rational expression for L( G). I would have to start by solving for B.
SO what i have done so far is:
S = bA + aB + 1
A = aA + bB
B = bA + aB + 1
B = b*(aA +1)
A = aA + bb*(aA+1)
= aA + bb*aA + bb*
= (a+bb*a)A + bb*
= (a+bb*a)*bb*
S = b(a+bb*a)*bb* + aB + 1
But from there I am not sure what to do, or even if I did the entire thing right. Also, how would I describe L(G)?