# Solve right linear set equations

Trying to solve this set of equations. I'm feeling like I'm making it so complicated. Of course + is union. Am I on the right track?

A = 0B + 1D
B = 0C + 1A
C = 0A + 1B + λ
D = OD + 1C + λ

A = 0B + 1(0*1C + 0*) = 0B + 10*1C + 10*
B = 0C + 1A
C = 0A + 1B + λ
D = OD + 1C + λ = 0*1C + 0*

A = 0(0C + 1A) + 10*1C + 10* = 00C + 01A + 10*1C + 10* = 01A + (00 + 10*1)C + 10* = (01)*((00 + 10*1)C + 10*)
B = 0C + 1A
C = 0A + 1B + λ

A = (01)*((00 + 10*1)C + 10*)
B = 0C + 1((01)*((00 + 10*1)C + 10*))
C = 0A + 1B + λ

A = (01)*((00 + 10*1)C + 10*)
B = 0C + 1((01)*((00 + 10*1)C + 10*))
C = 0((01)*((00 + 10*1)C + 10*)) + 1(0C + 1((01)*((00 + 10*1)C + 10*))) + λ

A = (01)*((00 + 10*1)C + 10*)
C = 0((01)*((00 + 10*1)C + 10*)) + 1(0C + 1((01)*((00 + 10*1)C + 10*))) + λ
C = 0(01)*(00 + 10*1)C + 0(01)10 + 10C + 11((01)*((00 + 10*1)C + 10*)) + λ
C = 0(01)*(00 + 10*1)C + 0(01)10 + 10C + 11(01)*(00 + 10*1)C + 11(01)10 + λ
C = (0(01)*(00 + 10*1) + 10 + 11(01)*(00 + 10*1))*(0(01)10 + 11(01)10)

A = (01)*((00 + 10*1)((0(01)*(00 + 10*1) + 10 + 11(01)*(00 + 10*1))*(0(01)10 + 11(01)10)) + 10*)
C = 0((01)*((00 + 10*1)C + 10*)) + 1(0C + 1((01)*((00 + 10*1)C + 10*))) + λ
C = 0(01)*(00 + 10*1)C + 0(01)10 + 10C + 11((01)*((00 + 10*1)C + 10*)) + λ
C = 0(01)*(00 + 10*1)C + 0(01)10 + 10C + 11(01)*(00 + 10*1)C + 11(01)10 + λ
C = (0(01)*(00 + 10*1) + 10 + 11(01)*(00 + 10*1))*((0(01)10 + 11(01)10) + λ)

A = (01)*(((00 + 10*1)((0(01)*(00 + 10*1) + 10 + 11(01)*(00 + 10*1))*((0(01)*10* + 11(01)*10*) + λ))) + 10*)

edit: fixed it.

-
So the task is to convert a regular grammar into a regular expression for the same language, right? (It looks like Markdown has eaten some of the stars in your final answer, by the way). –  Henning Makholm Nov 11 '12 at 15:30
@HenningMakholm yes. this is the task. I fixed my answer. Look right? this is the way? –  Mike Nov 11 '12 at 15:32
It may or may not be right but for sure it's ugly. Are you required to use a particular systematic procedure, or is it anything-goes? –  Henning Makholm Nov 11 '12 at 15:37

A -> 0B + 1D
B -> 0C + 1A
C -> 0A + 1B + λ
D -> 0D + 1C + λ


we can eliminate B

A -> 0(0C + 1A) + 1D
C -> 0A + 1(0C + 1A) + λ
D -> 0D + 1C + λ


and distribute

A -> 00C + 01A + 1D
C -> 0A + 10C + 11A + λ
D -> 0D + 1C + λ


and collect

A -> 00C + 01A + 1D
C -> (0+11)A + 10C + λ
D -> 0D + 1C + λ


now look at D, we can use the kleene star to eliminate the recursion

A -> 00C + 01A + 1D
C -> (0+11)A + 10C + λ
D -> (0)*1C + (0)*λ


and then eliminate it

A -> 00C + 01A + 1(0)*1C + 1(0)*λ
C -> (0+11)A + 10C + λ


and collect

A -> 01A + (00+1(0)*1)C + 1(0)*λ
C -> (0+11)A + 10C + λ


we can also make C non-recursive in the same way

A -> 01A + (00+1(0)*1)C + 1(0)*λ
C -> (10)*(0+11)A + (10)*λ


and then eliminate it

A -> 01A + (00+1(0)*1)((10)*(0+11)A + (10)*λ) + 1(0)*λ


and distribute

A -> 01A + (00+1(0)*1)(10)*(0+11)A + (00+1(0)*1)(10)*λ + 1(0)*λ


and collect

A -> (01+(00+1(0)*1)(10)*(0+11))A + (00+1(0)*1)(10)*λ + 1(0)*λ


and make it non-recursive

A -> (01+(00+1(0)*1)(10)*(0+11))*((00+1(0)*1)(10)*λ + 1(0)*λ)


now this is a regular expression.

-
Thank you very much. –  Mike Nov 11 '12 at 16:09
When "solving a system of equations" is it sufficient to give the solution to only one of the variables? –  Hendrik Jan Nov 11 '12 at 16:35
@HendrikJan, you can solve the rest if you want –  sperners lemma Nov 11 '12 at 16:55
@Spenrers, thanks. I understand. Assuming this is homework, I was wondering what the professor would expect as answer. –  Hendrik Jan Nov 11 '12 at 23:27

I would start by drawing the automaton to get an intuitive handle on what's going on:

It looks like the key states are A and C. We can write down an easy set of expressions for getting from one of A,C to another one without meeting A or C along the way:

{A2A} = 01
{A2C} = 10*1|00
{C2A} = 0|11
{C2C} = 10


Now, something that gets us from A to A once (with no intermediate As, but possibly Cs):

{AA} = {A2A} | {A2C}{C2C}*{C2A} = 01|(10*1|00)(10)*(0|11)


An finally an expression for the entire automaton:

L = {AA}* ( {A2D} | {A2C}{C2C}* ) =
( 01|(10*1|00)(10)*(0|11) )* ( 10* | (10*1|00)(10)* )

-
Thank you very much. –  Mike Nov 11 '12 at 16:08