1
$\begingroup$

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.

  • 0
    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?2012-11-11

2 Answers 2

1
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.

  • 0
    @Spenrers, thanks. I understand. Assuming this is homework, I was wondering what the professor would expect as answer.2012-11-11
2

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