Solving the corresponding semiring equations to derive a rational expression for L( G)

50 Views Asked by At

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)?