Need Regular Expression for Finite Automata: Even number of 1s and Even number of 0s

My problem may sounds different to you.

I am a beginner and I am learning Finite Automata. I am googing over Internet to find the Regular Expression for Finite Automata of Given Machine Below.

enter image description here

Can anyone help me to write "Regular Expression for Finite Automata" of above machine

Any help will be appreciated


How to write regular expression for a DFA using Arden theorem

Lets instead of language symbols 0,1 we take Σ = {a, b} and following is new DFA.

DFA
Notice start state is Q0

You have not given but In my answer initial state is Q0, Where final state is also Q0.

Language accepted by is DFA is set of all strings consist of symbol a and b where number of symbol a and b are even (including Λ).

Some example strings are {Λ, aa, bb, abba, babbab }, there is no constraint of order and patter of appearance of symbol just both should be even number of time.
note: Λ is allowed because numberOf(a) and numberOf(b) is zero that is even.

As I said in my lined answer: How to write regular expression for a DFA every state stores some information. Below is a what information is stored in each state in above DFA.

Q0: Even number of a and even number of b
Q1: Odd number of a and even number of b
Q2: Odd number of a and odd number of b
Q3: Even number of a and odd number of b

(You can make DFAs for more interesting languages by changing set of final sates)
One should read the lined answer, because my approach to fined RE for DFA in both answer is different

What is a Regular Expression?
The approach is explained below using Arden's Theorem, applicable on a transition diagram in which there is a single start state and no null move defined (our DFA is in this form). The technique is explained in a book: Formal Languages And Automata Theory

Remember 4.2 ARDEN THEOREM:

Let B and C be are two Regular Expressions over Σ. If C does not contain Λ, then for the equation A = B + AC has a unique (one and only one) solution A = BC*.

[Solution]:

Step-1: Write initial equation, one equation for corresponding to each state in DFA. This equation means how a state can be reach in a single step

So according to our DFA following 4-equations are possible:

  1. Q0 = Λ + Q1a + Q3b
  2. Q1 = Q0a + Q2b
  3. Q2 = Q1b + Q3a
  4. Q3 = Q0b + Q2a

In equation (1) extra Λ is because Q0 is initial state, can be reached without any input (a point of start). Because Q0 is also only a final state, a string consist of a, b is acceptable if it ends at Q0. Value of Q0 will give us required regular expression so our target is to simply equation-(1) in terms of a, b.

Step-2: Simplify equation using by putting value of states from other equations and using Arden's simplification equation.

Lets we first take equation-(4) and replace value of Q2 from equation-(3).

Q3 = Q0b + Q2a
Q3 = Q0b + (Q1b + Q3a) a
Q3 = Q0b + Q1ba + Q3aa

The last equation can be view in the form of Arden's equation A = B + AC. Where A is Q3, B = Q0b + Q1ba and C = aa. So according to Arden's therm, equation Q3 = Q0b + Q1ba + Q3aa has a unique solution that is:

Q3 = (Q0b + Q1ba)(aa)*

Or one can write this as follows:

5. Q3 = Q0b(aa)* + Q1ba(aa)*

Logically you can check/understand eq-(5) means Q3 can be reached in two ways (+) fist from by applying b on Q0 then there is a loop with label aa on Q3, second way is from Q1 with application of ba.

In similar ways, we can simplify equation-(2)

Q1 = Q0a + Q2b
Q1 = Q0a + (Q1b + Q3a)b
Q1 = Q0a + Q1bb + Q3ab

Use Arden's simplification rules here.

Q1 = (Q0a + Q3ab)(bb)*

further simplify

6. Q1 = Q0a(bb)* + Q3ab(bb)*

Now value of Q3 from equation-(5) into equation-(6)

Q1 = Q0a(bb)* + (Q0b(aa)* + Q1ba(aa)* )ab(bb)*
Q1 = Q0a(bb)* + Q0b(aa)* ab(bb)* + Q1ba(aa)* ab(bb)*

Again improve this last equation using Arden law of simplification.

Q1 = (Q0a(bb)* + Q0b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

take Q0 conman:

7. Q1 = Q0(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

Can you understand this equation, Its how you can go to Q1 from state Q0? We remember this solution as equation-(7)

As above we can evaluate value of Q1 in terms of state Q0 and a, b, Similarly we are to evaluate value for state Q3. For this we can simple put value of state Q1 from equation-(5) into equation-(7).

5. Q3 = Q0b(aa)* + Q1ba(aa)*
. Q3 = Q0b(aa)* + Q0(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)*
8. Q3 = Q0 ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* )

Now, in equation number (1) put value of state Q3 and Q1 from equation number (8) and (7) receptively.

Q0 = Λ + Q1a + Q3b
Q0 = Λ + Q0(a(bb)* + (aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + Q0 ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* ) b

Now, Last time apply Arden solution to find value of state Q0 in terms of symbols a and b.

Q0 = Λ + ( (a(bb)* + (aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* ) b )*

that is same as (we can discard Λ here) RE:

( (a(bb)* + (aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* ) b )*

This is the RE you where looking for.

I am not sure that it can be further simplified. I am leaving it as an exercise for you.

In linked question I suggested a non-formal and analytical method but it was hard to apply and find RE for this DFA and this question demonstrate power of Arden's theorem and step by step solution.

Edit:

My previous regular expression is correct but hard to grapes because unsymmetrical form. Below I am writing new form of RE that is more symmetrical.

We have equation-(5), (6) as follows:

5. Q3 = Q0b(aa)* + Q1ba(aa)*
6. Q1 = Q0a(bb)* + Q3ab(bb)*

Both are symmetrical in construction and easy to learn. (read my comment after eq-(5) above)

To evaluate value of state Q1 in terms of Q0, I putted value of Q3 from equation-(5) into equation-(6) that gives me equation-(7) as follows:

7. Q1 = Q0(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

Similarly, to evaluate value of state Q3 in terms of Q0, we can put value of Q1 from equation-(6) into equation-(5) that will give us new form of equation-(8) as follows:

Q3 = Q0b(aa)* + Q1ba(aa)*
Q3 = Q0b(aa)* + (Q0a(bb)* + Q3ab(bb)* ) ba(aa)*
Q3 = Q0b(aa)* + Q0a(bb)* ba(aa)* + Q3ab(bb)* ba(aa)*

Now, we can have equation-(8) in our desired form:

8. Q3 = Q0(b(aa)* + a(bb)* ba(aa)* )(ab(bb)* ba(aa)* )*

Now, we have equation-(1), (7), (8):

1. Q0 = Λ + Q1a + Q3b
7. Q1 = Q0(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*
8. Q3 = Q0(b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )*

Now, we can have equation-(8) in our desired form:

8. Q3 = Q0(b(aa)* + a(bb)* ba(aa)* )(ab(bb)* ba(aa)* )*

Now, we have equation-(1), (7), (8):

1. Q0 = Λ + Q1a + Q3b
7. Q1 = Q0(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*
8. Q3 = Q0(b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )*

Now put value of state Q1 and Q3 into equation-(1):

Q0 = Λ + Q0(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + Q0(b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )* b

can also be written as:

Q0 = Λ + Q0 ( (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + (b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )* b )

Next, apply Arden's theorem on this equation, and we get the final RE:

Regular Expression for even numbers of 'a' and even numbers of 'b':

( (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + (b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )* b )*

Can one step further simplified as below:

((a + b(aa)*ab)(bb)*(ba(aa)*ab(bb)*)*a + (b + a(bb)*ba)(aa)*(ab(bb)*ba(aa)*)*b)*

Let E is the language with even number of a's and even number of b's, and below is the Regular expression for language E.

[00 + 11 + (01+10)(11+00)(01+10)]

00 = type1

11 = type2

(01+10)(00+11)*(01+10) = type3

Suppose that we are scanning along a word in the language of E from left to right reading the letters two at a time. First we come to a double 0 (type1), then to a double 1 (type2) , then to another double 0 (type 1 again). Then perhaps we come upon a pair of letters that are not the same. Say, for instance, that the next two letters are 10. This must begin a substring of type3. It starts with an undoubled pair (either 01 or 10), then it has a section of doubled letters (many repetitions of either 00 or 11), and then it finally ends with another undoubled pair (either 01 or 10 again). One property of this section of the word is that it has an even number of 0's and an even number of 1's. If the section started with a 10, it could end with an 01 still giving two 0's and two 1's on the ends with only doubled letters in between. If it started with a 10 and ended with an 01, again, it would give an even number of 0's and an even number of 1's. After this section of type3 we could proceed with more sections of type, or type2 until we encountered another undoubled pair, starting another type3 section. We know that another undoubled pair will be coming up to balance off the initial one. The total effect is that every word of the language of E contains an even number of 0's and an even number of 1's