Đ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 note Theory of automata - Lecture 26 Lecture 2 Theory Of Automata By Dr. MM Alam 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 however each word has finite length. .