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

Lecture Theory of automata - Lecture 26 includes contents: Example of nonregular language, pumping lemma version I, proof, examples. | Lecture # 2 Theory Of Automata By Dr. MM Alam 1 Lecture#1 Recap Definition of the word Automata Types of languages, empty/Null String, Alphabets, words, length of strings, Palindromes How to form palindromes of even and odd length. Question Q) Prove that there are as many palindromes of length 2n, defined over Σ = {a,b,c}, as there are of length 2n-1, n = 1,2,3 . Determine the number of palindromes of length 2n defined over the same alphabet as well. Example:- L={aa,ab,ac,bb,ba,bc,cc,ca,cb} = 9 words. Solution Since the number of symbols are 3 in the alphabet, therefore, the length of 2n palindromes will be 3n. As 2n means that palindromes are of even length. Solution (Cont’d) Similarly, for palindromes of length 2n-1, we need to calculate their number for each respective symbol in the alphabet, that is, the required number of palindromes are 3n-1 for symbol a Similarly the number of palindromes of length 2n-1, with b or c as middle letter, will be 3n-1 as well. Hence the total . | Lecture # 2 Theory Of Automata By Dr. MM Alam 1 Lecture#1 Recap Definition of the word Automata Types of languages, empty/Null String, Alphabets, words, length of strings, Palindromes How to form palindromes of even and odd length. Question Q) Prove that there are as many palindromes of length 2n, defined over Σ = {a,b,c}, as there are of length 2n-1, n = 1,2,3 . Determine the number of palindromes of length 2n defined over the same alphabet as well. Example:- L={aa,ab,ac,bb,ba,bc,cc,ca,cb} = 9 words. Solution Since the number of symbols are 3 in the alphabet, therefore, the length of 2n palindromes will be 3n. As 2n means that palindromes are of even length. Solution (Cont’d) Similarly, for palindromes of length 2n-1, we need to calculate their number for each respective symbol in the alphabet, that is, the required number of palindromes are 3n-1 for symbol a Similarly the number of palindromes of length 2n-1, with b or c as middle letter, will be 3n-1 as well. Hence the total number of palindromes of length 2n-1 will be : 3n-1 + 3n-1 + 3n-1 = 3 (3n-1)= 3n . Consider the language of Palindrome over the alphabet {a,b}. Prove that if x is in PALINDROME then so is xn for any n. Example: suppose x = aba and is a palindrome and xr = (aba)r = aba Then: (aba)5 = (aba aba aba aba aba aba)r =aba aba aba aba aba which is again a palindrome Proof. It is true for n = 0 by assumption xn is palindrome. Assume that it is true for n-1 namely xn-1 is in palindrome and (xn-1)r = xn-1. Now as we know that (xy)r = yrxr . (xn )r = (xn-1x)r = xr (xn-1)r = x xn-1 = xn. Thus, xn is in palindrome Kleene Star closure In order to further generalize the notation of any combination of strings the famous logician kleene and founder of the ‘Theory of Automata’ subject has introduced a notation called kleene closure. It is denoted by Σ*and represent all collection of strings defined over Σ including Null string. The language produced by Kleene closure is infinite. It contains infinite words, .