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

1Lecture-2 Recap Lecture-1 Introduction to the course title, Formal and In- formal languages, Alphabets, Strings, Null string, Words, Valid and In-valid alphabets, length of a string, Reverse of a string, Defining languages, Descriptive definition of languages, EQUAL, EVEN-EVEN, INTEGER, EVEN, { an bn}, { an bn an }, factorial, FACTORIAL, DOUBLEFACTORIAL, SQUARE, DOUBLESQUARE, PRIME, PALINDROME. 2Task 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. 3Solution To calculate the number of palindromes of length(2n), consider the following diagram, 4which shows that there are as many palindromes of length 2n as there are the strings of length n i.e. the required number of palindromes are 3n (as there are three letters in the given alphabet, so the number of strings of length n will be 3n ). 5To calculate the number of palindromes of length (2n-1) with a as the middle letter, consider the following diagram, 6which shows that there are as many palindromes of length 2n-1, with a as middle letter, as there are the strings of length n-1, i.e. the required number of palindromes are 3n-1. 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 . 7Kleene Star Closure Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted by Σ*, is the collection of all strings defined over Σ, including Λ. It is to be noted that Kleene Star Closure can be defined over any set of strings. 8Examples  If Σ = {x} Then Σ* = {Λ, x, xx, xxx, xxxx, .}  If Σ = {0,1} Then Σ* = {Λ, 0, 1, 00, 01, 10, 11, .}  If Σ = {aaB, c} d Then Σ* = {Λ, aaB, c, aaBaaB, aaBc, caaB, cc, .} 9Note Languages generated by Kleene Star Closure of set of strings, are infinite languages. (By infinite language, it is supposed that the language contains infinite many words, each of finite length). 10 Task Q) 1) Let S={ab, bb} and T={ab, bb, bbbb} Show that S* = T* [Hint S*  T* and T*  S*] 2) Let S={ab, bb} and T={ab, bb, bbb} Show that S* ≠ T* But S*  T* 3) Let S={a, bb, bab, abaab} be a set of strings. Are abbabaabab and baabbbabbaabb in S*? Does any word in S* have odd number of b’s? 11 PLUS Operation (+) Plus Operation is same as Kleene Star Closure except that it does not generate Λ (null string), automatically. Example:  If Σ = {0,1} Then Σ+ = {0, 1, 00, 01, 10, 11, .} If Σ = {aab, c} Then Σ+ = {aab, c, aabaab, aabc, caab, cc, .} 12 TASK Q1)Is there any case when S+ contains Λ? If yes then justify your answer. Q2) Prove that for any set of strings S i. (S+)*=(S*)* ii. (S+)+=S+ iii. Is (S*)+=(S+)* 13 Remark It is to be noted that Kleene Star can also be operated on any string i.e. a* can be considered to be all possible strings defined over {a}, which shows that a* generates Λ, a, aa, aaa, It may also be noted that a+ can be considered to be all possible non empty strings defined over {a}, which shows that a+ generates a, aa, aaa, aaaa, 14 Defining Languages Continued  Recursive definition of languages The following three steps are used in recursive definition 1. Some basic words are specified in the language. 2. Rules for constructing more words are defined in the language. 3. No strings except those constructed in above, are allowed to be in the language. 15 Example Defining language of INTEGER Step 1: 1 is in INTEGER. Step 2: If x is in INTEGER then x+1 and x-1 are also in INTEGER. Step 3: No strings except those constructed in above, are allowed to be in INTEGER. 16 Example Defining language of EVEN Step 1: 2 is in EVEN. Step 2: If x is in EVEN then x+2 and x-2 are also in EVEN. Step 3: No strings except those constructed in above, are allowed to be in EVEN. 17 Example Defining the language factorial Step 1: As 0!=1, so 1 is in factorial. Step 2: n!=n*(n-1)! is in factorial. Step 3: No strings except those constructed in above, are allowed to be in factorial. 18 Defining the language PALINDROME, defined over Σ = {a,b} Step 1: a and b are in PALINDROME Step 2: if x is palindrome, then s(x)Rev(s) and xx will also be palindrome, where s belongs to Σ* Step 3: No strings except those constructed in above, are allowed to be in palindrome 19 Defining the language {anbn }, n=1,2,3, , of strings defined over Σ={a,b} Step 1: ab is in {anbn} Step 2: if x is in {anbn}, then axb is in {anbn} Step 3: No strings except those constructed in above, are allowed to be in {anbn} 20 Defining the language L, of strings ending in a , defined over Σ={a,b} Step 1: a is in L Step 2: if x is in L then s(x) is also in L, where s belongs to Σ* Step 3: No strings except those constructed in above, are allowed to be in L 21 Defining the language L, of strings beginning and ending in same letters , defined over Σ={a, b} Step 1: a and b are in L Step 2: (a)s(a) and (b)s(b) are also in L, where s belongs to Σ* Step 3: No strings except those constructed in above, are allowed to be in L 22 Defining the language L, of strings containing aa or bb , defined over Σ={a, b} Step 1: aa and bb are in L Step 2: s(aa)s and s(bb)s are also in L, where s belongs to Σ* Step 3: No strings except those constructed in above, are allowed to be in L 23 Defining the language L, of strings containing exactly aa, defined over Σ={a, b} Step 1: aa is in L Step 2: s(aa)s is also in L, where s belongs to b* Step 3: No strings except those constructed in above, are allowed to be in L 24 Summing Up Kleene Star Closure, Plus operation, recursive definition of languages, INTEGER, EVEN, factorial, PALINDROME, {anbn}, languages of strings (i) ending in a, (ii) beginning and ending in same letters, (iii) containing aa or bb (iv)containing exactly aa,