For this we can simple put value of state Q 1 from equation-(5) into equation-(7). Q 1 = Q 0(a(bb)* + b(aa)* ab(bb)* ) (ba(aa)* ab(bb)* )*Ĭan you understand this equation, Its how you can go to Q 1 from state Q 0? We remember this solution as equation-(7)Īs above we can evaluate value of Q 1 in terms of state Q 0 and a, b, Similarly we are to evaluate value for state Q 3. Q 1 = Q 0a(bb)* + Q 0b(aa)* ab(bb)* + Q 1ba(aa)* ab(bb)*Īgain improve this last equation using Arden law of simplification. Now value of Q 3 from equation-(5) into equation-(6) In similar ways, we can simplify equation-(2) Logically you can check/understand eq-(5) means Q 3 can be reached in two ways ( +) fist from by applying b on Q 0 then there is a loop with label aa on Q 3, second way is from Q 1 with application of ba. So according to Arden's therm, equation Q 3 = Q 0b + Q 1ba + Q 3aa has a unique solution that is: Where A is Q 3, B = Q 0b + Q 1ba and C = aa. The last equation can be view in the form of Arden's equation A = B + AC. Lets we first take equation-(4) and replace value of Q 2 from equation-(3). Step-2: Simplify equation using by putting value of states from other equations and using Arden's simplification equation. Value of Q 0 will give us required regular expression so our target is to simply equation-(1) in terms of a, b. In equation (1) extra Λ is because Q 0 is initial state, can be reached without any input (a point of start).īecause Q 0 is also only a final state, a string consist of a, b is acceptable if it ends at Q 0. So according to our DFA following 4-equations are possible: This equation means how a state can be reach in a single step Step-1: Write initial equation, one equation for corresponding to each state in DFA. If C does not contain Λ, then for the equation A = B + AC has a unique (one and only one) solution A = BC*.
Let B and C be are two Regular Expressions over Σ. The technique is explained in a book: Formal Languages And Automata Theory
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). One should read the lined answer, because my approach to fined RE for DFA in both answer is different ( You can make DFAs for more interesting languages by changing set of final sates) Q 3: Even number of a and odd number of b Q 1: Odd number of a and even number of b Q 0: Even number of a and even number of b Below is a what information is stored in each state in above DFA.
#Finite state automata with a b c how to#
Note: Λ is allowed because numberOf( a) and numberOf( b) is zero that is even.Īs I said in my lined answer: How to write regular expression for a DFA every state stores some information. Lets instead of language symbols 0, 1 we take Σ =, there is no constraint of order and patter of appearance of symbol just both should be even number of time. How to write regular expression for a DFA using Arden theorem
0 kommentar(er)
