Đang chuẩn bị liên kết để tải về tài liệu:
Lecture note Theory of automata - Lecture 27

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 note Theory of automata - Lecture 27 Lecture 3 Theory Of Automata By Dr. MM Alam 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 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 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 concatenate two words in L and get another word in L if and only if the words are not the same. That is for any words w1 and w2 in L where w1 w2 the word w1w2 is in L but the word w1w1 is not in L. Prove that this cannot happen. w1 L and w2 L 2 different words therefore w1 w2 L w1w2 L and w1 L 2 different words Let us define S S Is this set bigger .