Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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) + λ)

Final Answer
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.

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted
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.

share|improve this answer
    
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:

diagram of finite automaton

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)* )
share|improve this answer
    
Thank you very much. –  Mike Nov 11 '12 at 16:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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