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

1Recap lecture 29 Example of prefixes of a language, Theorem: pref(Q in R) is regular, proof, example, Decidablity, deciding whether two languages are equivalent or not ?, method 1, example, method 2, example 2Example Consider two languages L1 and L2, expressed by the REs r1=a * and r2=+aa * respectively. To determine whether L1 and L2 are equivalent, let the corresponding FAs be b a a a,b r1 r2 r3+ b FA2p1 p2 b a a,b FA1 3Example continued As discussed earlier, the FA corresponding to the language (L1L2 c)U(L1 cL2) helps in this regard i.e. if this FA accepts any word then L1 and L2 are not equivalent other wise L1 and L2 are equivalent. Following are the FAs corresponding to L1 c and L2 c 4Example continued FAs corresponding to (FA1 c U FA2) c and (FA2 c U FA1) c may be as follows q1- q2+ b a a,b FA1 c b a a a,b s1- s2+ s3 bFA2 c 5Example continued Both the FAs have no final state, so these FAs accept nothing. This implies that their union will not also accept any string. Hence FA corresponding to the language (L1L2 c)U(L1 cL2) accepts nothing. Thus both the languages are equivalent. b a a a,b - b (FA1 cUFA2) c b a a a,b - b (FA2 cUFA1) c q1 , r1 q1 , r3 q2 , r2 p1 , s1 p2 , s2 p1 , s3 6Example Following is an FA, for which it is required to decide whether it accepts any string or not? Using steps discussed in method 2, the following FA can be checked whether it accepts any word or not. 7Example 1- 2 3 4+ 5 6 a a a a a b b b b a,b b 8Example continued 1- 2 3 4+ 5 6 a a a a a b b b b a,b b 9Example continued 1- 2 3 4+ 5 6 a a a a b b b a,b b 10 Example continued 1- 2 3 4+ 5 6 a a a b b a,b b 11 Example continued 1- 2 3 4+ 5 6 a a a b b b 12 Example continued As no final state of the previous FA is marked, after applying the method, so the given FA accepts no word. 13 Method 3 If the FA has N states, then test the words of length less than N. If no word is accepted by this FA, then it will accept no word. Note: It is to be noted that all the methods discussed above, to determine whether an FA accepts certain word, are effective procedures. Example: To determine whether the following FA accepts certain word, using method 3, all the strings of length less than 4 (i.e. less than the number of states of the FA) are sufficient to be tested 14 Example 3 2 4 +1- a a a b a b b b i.e. , a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb are required to be tested. 15 Example continued It can be observed that the strings aa, baa, aaa are accepted by this FA, hence the language accepted by this FA is not empty. Following is another example, to test whether an FA accepts certain word ? 16 Example Consider the following FA. To determine whether this FA accepts some word, all the strings of length less than 4 (i.e. less than the number of states of this FA) are to be tested 3 4+ a,b b b 1- 2 aa a,bb 17 Example continued It can be observed that none of the strings , a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, is accepted by this FA. Thus the given FA cannot accept any word. 18 Observation To find whether a regular expression defines an infinite language or not ? The following possibilities are required to be checked. If a regular expression contains * then it may define an infinite language, with the exception * as *= e.g. (+a*)(*+)* defines finite language. While (*+a*)* (*+)* defines an infinite language. There are so many ways to decide whether an FA accepts a finite language or an infinite. Following is a theorem regarding this 19 Theorem Let F be an FA having N states 1. If F accepts a word w s.t. N  length(w) < 2N then F accepts infinite language. 2. If F accepts an infinite language then there are some words w s.t. N  length(w) < 2N The first part can be proved, using the pumping lemma version II. Following is a remark regarding this theorem 20 Remark There is an effective procedure to decide whether an FA accepts finite or infinite language. For a machine with N number of states, the total number of strings to be tested, defined over an alphabet of m letters, is mN +mN+1 + mN+2 + +m2N-1. After testing all these strings on the machine, if any is accepted then the machine accepts infinite language other wise not. e.g. for machine of three states and alphabet of two letters, 2 3 +2 4 +2 5 = 56 strings are to be tested. 21 Summing Up Deciding whether two languages are equivalent or not, example, deciding whether an FA accept any string or not, method 3, examples, finiteness of a language