The following will be discussed in this chapter: Pumping lemma version II, example of pumping lemma version II, Myhill Nerode theorem, example of Myhill Nerode theorem, Instruction for saad. | Lecture # 3 Theory Of Automata By Dr. MM Alam 1 Lecture#2 Recap Kleene Closure Examples of Kleene Closure. Plus Operation Prove that for all sets S, (i) (S+)* = (S*)* (ii) (S+)+ = S+ (iii) Is (S*)+ = (S+)* for all sets S? S+ = {all concatenations of words in S, excluding Λ}. (S+)* = {Λ and all concatenations of words in S+} = {Λ and all concatenations of (concatenations of words in S, excluding Λ)} = {Λ and all concatenations of words in S} = S* S* = {Λ and all concatenations of words in S} (S*)* = {Λ and all concatenations of words in S} = {Λ and all concatenations of (Λ and all concatenations of words in S)} = {Λ and all concatenations of words in S} = S* Therefore (S+)* = (S*)* = S* (ii) (S+)+ = S+ S+ = {all concatenations of words in S, excluding Λ} (S+)+ = {all concatenations of words in S+, excluding Λ} = {all concatenations of (all concatenations of words in S, excluding Λ) excluding Λ)} = {all concatenations of words in S, excluding Λ} = S+ (iii) Is (S*)+ = (S+)* for all sets | Lecture # 3 Theory Of Automata By Dr. MM Alam 1 Lecture#2 Recap Kleene Closure Examples of Kleene Closure. Plus Operation Prove that for all sets S, (i) (S+)* = (S*)* (ii) (S+)+ = S+ (iii) Is (S*)+ = (S+)* for all sets S? S+ = {all concatenations of words in S, excluding Λ}. (S+)* = {Λ and all concatenations of words in S+} = {Λ and all concatenations of (concatenations of words in S, excluding Λ)} = {Λ and all concatenations of words in S} = S* S* = {Λ and all concatenations of words in S} (S*)* = {Λ and all concatenations of words in S} = {Λ and all concatenations of (Λ and all concatenations of words in S)} = {Λ and all concatenations of words in S} = S* Therefore (S+)* = (S*)* = S* (ii) (S+)+ = S+ S+ = {all concatenations of words in S, excluding Λ} (S+)+ = {all concatenations of words in S+, excluding Λ} = {all concatenations of (all concatenations of words in S, excluding Λ) excluding Λ)} = {all concatenations of words in S, excluding Λ} = S+ (iii) Is (S*)+ = (S+)* for all sets S? S* = {Λ and all concatenations of words in S} (S*)+ = {all concatenations of words in S*, but not Λ} S* already contains Λ, so (S*)+ contains Λ too, since it’s part of the language. No new words are added with the + operator, so (S*)+ = S*. S+ = {all concatenations of words in S, without Λ} (S+)* = {Λ and all concatenations of words in S+} = {Λ and all concatenations of (all concatenations of words in S, not Λ)} = {Λ and all concatenations of words in S} = S* The external * operator only added Λ to the language. Therefore (S*)+ = (S+)* = S*. Let S = {a, bb, bab, abaab}. Is abbabaabab in S*? Is abaabbabbaab? Does any word in S* have an odd total number of b’s? (a)(bb)(abaab)ab can’t be factored into substrings from S, so it is not in the language. (abaab)(bab)b (a)(a)(bb) can’t be factored into substrings from S, so it’s not in the language. It is not possible to have an odd no of b’s. The reason is that even b’s +even b’s = even b’s Suppose that for some language L we can always .
