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

Question

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.

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

Any help will be appreciated

Answer 1

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.

Notice start state is Q₀

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

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.

Q₀: Even number of a and even number of b
Q₁: Odd number of a and even number of b
Q₂: Odd number of a and odd number of b
Q₃: 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. Q₀ = Λ + Q₁a + Q₃b
2. Q₁ = Q₀a + Q₂b
3. Q₂ = Q₁b + Q₃a
4. Q₃ = Q₀b + Q₂a

In equation (1) extra Λ is because Q₀ is initial state, can be reached without any input (a point of start). Because Q₀ is also only a final state, a string consist of a, b is acceptable if it ends at Q₀. Value of Q₀ 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 Q₂ from equation-(3).

Q₃ = Q₀b + Q₂a
Q₃ = Q₀b + (Q₁b + Q₃a) a
Q₃ = Q₀b + Q₁ba + Q₃aa

The last equation can be view in the form of Arden's equation A = B + AC. Where A is Q₃, B = Q₀b + Q₁ba and C = aa. So according to Arden's therm, equation Q₃ = Q₀b + Q₁ba + Q₃aa has a unique solution that is:

Q₃ = (Q₀b + Q₁ba)(aa)*

Or one can write this as follows:

5. Q₃ = Q₀b(aa)* + Q₁ba(aa)*

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

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

Q₁ = Q₀a + Q₂b
Q₁ = Q₀a + (Q₁b + Q₃a)b
Q₁ = Q₀a + Q₁bb + Q₃ab

Use Arden's simplification rules here.

Q₁ = (Q₀a + Q₃ab)(bb)*

further simplify

6. Q₁ = Q₀a(bb)* + Q₃ab(bb)*

Now value of Q₃ from equation-(5) into equation-(6)

Q₁ = Q₀a(bb)* + (Q₀b(aa)* + Q₁ba(aa)* )ab(bb)*
Q₁ = Q₀a(bb)* + Q₀b(aa)* ab(bb)* + Q₁ba(aa)* ab(bb)*

Again improve this last equation using Arden law of simplification.

Q₁ = (Q₀a(bb)* + Q₀b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

take Q₀ conman:

7. Q₁ = Q₀(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

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

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

5. Q₃ = Q₀b(aa)* + Q₁ba(aa)*
. Q₃ = Q₀b(aa)* + Q₀(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)*
8. Q₃ = Q₀ ( b(aa)* + (a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* ba(aa)* )

Now, in equation number (1) put value of state Q₃ and Q₁ from equation number (8) and (7) receptively.

Q₀ = Λ + Q₁a + Q₃b
Q₀ = Λ + Q₀(a(bb)* + (aa)* ab(bb)* ) (ba(aa)* ab(bb)* )* a + Q₀ ( 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 Q₀ in terms of symbols a and b.

Q₀ = Λ + ( (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. Q₃ = Q₀b(aa)* + Q₁ba(aa)*
6. Q₁ = Q₀a(bb)* + Q₃ab(bb)*

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

To evaluate value of state Q₁ in terms of Q₀, I putted value of Q₃ from equation-(5) into equation-(6) that gives me equation-(7) as follows:

7. Q₁ = Q₀(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*

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

Q₃ = Q₀b(aa)* + Q₁ba(aa)*
Q₃ = Q₀b(aa)* + (Q₀a(bb)* + Q₃ab(bb)* ) ba(aa)*
Q₃ = Q₀b(aa)* + Q₀a(bb)* ba(aa)* + Q₃ab(bb)* ba(aa)*

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

8. Q₃ = Q₀(b(aa)* + a(bb)* ba(aa)* )(ab(bb)* ba(aa)* )*

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

1. Q₀ = Λ + Q₁a + Q₃b
7. Q₁ = Q₀(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*
8. Q₃ = Q₀(b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )*

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

8. Q₃ = Q₀(b(aa)* + a(bb)* ba(aa)* )(ab(bb)* ba(aa)* )*

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

1. Q₀ = Λ + Q₁a + Q₃b
7. Q₁ = Q₀(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*
8. Q₃ = Q₀(b(aa)* + a(bb)* ba(aa)* ) (ab(bb)* ba(aa)* )*

Now put value of state Q₁ and Q₃ into equation-(1):

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

can also be written as:

Q₀ = Λ + Q₀ ( (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)*