Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

like image 789
jyoti Avatar asked Jul 02 '13 07:07

jyoti


1 Answers

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)*
like image 172
Grijesh Chauhan Avatar answered Sep 20 '22 20:09

Grijesh Chauhan