Bài giảng Theory Of Automata - Lecture 17

1Recap Lecture 16 • Examples of Kleene’s theorem part III (method 3), NFA, examples, avoiding loop using NFA, example, converting FA to NFA, examples, applying an NFA on an example of maze, NFA with null string, examples, RE corresponding to NFA with null string (task), converting NFA to FA (method 1,2,3) examples, NFA and Kleene’s theorem method 1, examples, NFA and Kleene’s theorem method 2, examples 2Task • Determine the regular expression of the following NFA- a  1- 4+ b 5 a a a , b a 2 3 3Solution of the Task To eliminate state 5 the above NFA- may be reduced to the following a  1- 4+ b 5 a a a , b a 2 3 4Solution continued To eliminate state 2 the above NFA- may be reduced to the following a 1- 4+a +b 2 3 +aa*a ba*a 5Solution continued To eliminate state 3 the above NFA- may be reduced to the following ba*a 3 a(+aa*a) 4+ 1- a(+aa*a)+b 6Solution continued Hence the RE is a(+aa*a)+(+b)(a(+aa*a)+ba*a) Which may be reduced to a+aaa*a+ba*a+ba+baaa*a +bba*a OR a+aaa*a+ba*a+baaa*a +bba*a 1- a(+aa*a)+(+b)(a(+aa*a)+ba*a) 4+ 7Task • Build an FA corresponding to the following NFA which accepts the language of strings containing bb b b 3+1- 2 a, b a, b 8Solution of the Task a a b 1- a b a b b(1,2) (1,2,3) + (1,3)+ It may be noted that the above method seems to be complicated, hence an easier method discussed by Martin, follows as b b 3+1- 2 a, b a, b 9NFA to FA continued Method 3: As discussed earlier that in an NFA, there may be more than one transition for a certain letter and there may not be any transition for certain letter, so starting from the initial state corresponding to the initial state of given NFA, the transition table along with new labels of states, of the corresponding FA, can be built introducing an empty state for a letter having no transition at certain state and a state corresponding to the combination of states, for a letter having more than one transitions. Following are the examples 10 Example • Consider the following NFA which accepts the language of strings containing bb Using the method discussed earlier, the transition table corresponding to the required FA may be constructed as b b x3+ x1- x2 a, b a, b 11 Example continued (x1 ,x2,x3)z3(x1 ,)x1z1z2(x1,x2) (x1,x2)z2x1z1z1x1 (x1 ,x2,x3)z3(x1,x3)z4z3+(x1,x2,x3) (x1 ,x2,x3)z3(x1,x3)z4z4+ (x1,x3) ba New States after reading Old States The corresponding transition diagram follows as 12 Example continued a ba z1- a b a b bz2 z3+ z4+ 13 NFA and Kleene’s Theorem It has been discussed that, by Kleene’s theorem part III, there exists an FA corresponding to a given RE. If the given RE is as simple as r=aa+bbb or r=a(a+b)*, the corresponding FAs can easily be constructed. However, for a complicated RE, the RE can be decomposed into simple REs corresponding to which the FAs can easily be constructed and hence, using the method, constructing the FAs corresponding to sum, concatenation and closure of FAs, the required FA can also be constructed. It is to be noted that NFAs also help in proving Kleene’s theorem part III, as well. Two methods are discussed in the following. 14 Method 1: The method is discussed considering the following example. Example:To construct the FAs for the languages L1= {a}, L2= {b} and L3= {} Step 1: Build NFA1, NFA2 and NFA3 corresponding to L1, L2 and L3 , respectively as shown in the following diagram NFA and Kleene’s Theorem 15 NFA and Kleene’s Theorem (method 1 ) continued • NFA1 • NFA2 • NFA3 a- + b- +  16 NFA and Kleene’s Theorem (method 1 ) continued Step 2: As discussed earlier for every NFA there is an FA equivalent to it, hence there must be FAs for the above mentioned NFAs as well. The corresponding FAs can be considered as follows 17 NFA and Kleene’s Theorem (method 1 ) continued b a,b + a –– a a,b a,b + b –– a,b  1a,b a,b 1 1 FA1 FA2 FA3 18 NFA and Kleene’s Theorem method 2 It may be observed that if an NFA can be built corresponding to union, concatenation and closure of FAs corresponding to the REs, then converting the NFA, thus, obtained into an equivalent FA, this FA will correspond to the given RE. Followings are the procedures showing how to obtain NFAs equivalent to union, concatenation and closure of FAs 19 Method: Introduce a new start state and connect it with the states originally connected with the old start state with the same transitions as the old start state, then remove the –ve sign of old start state. This creates non- determinism and hence results in an NFA. NFA corresponding to Union of FAs 20 Example • FA1 • FA2 a a a a b x1- x2 x4+ x3 b b b b a a, b y1- y2+ 21 a a a a b x1 x2 x4+ x3 b b b - b a a, b y1 y2+ a b ba NFA equivalent to FA1UFA2 22 Summing Up • converting NFA to FA (method 3), example, NFA and Kleene’s theorem method 1, examples, NFA and Kleene’s theorem method 2 , NFA corresponding to union of FAs,example