1. Lecture # 2 Theory Of Automata By Dr. MM Alam
2. 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.
3. 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.
4. 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.
5. 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 .
6. 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
7. 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
8. 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.
9. • The language produced by Kleene closure is infinite. It contains infinite words, however each word has finite length.
10. Examples • If Σ = {x} Then Σ* = {Λ, x, xx, xxx, xxxx, ….} • If Σ = {0,1} Then Σ* = {Λ, 0, 1, 00, 01, 10, 11, ….} • If Σ = {aaB, c} Then Σ* = {Λ ,aaB, c, aaBaaB, aaBc, caaB, cc, ….}
11. Q) Consider the language S*, where S = {a b}. How many words does this language have of length 2? of length 3? of length n? A) Number of words = nm Length 2: 22 = 4 Length 3: 23= 8 Length n: 2n
12. • Consider the language S*, where S = {aa b}. How many words does this language have of length 4? of length 5? of length 6? What can be said in general? Words of length 0: Λ = 1 word Words of length 1: b = 1 word Words of length 2: (Add aa to all words of length 0 --> 0 + 2 = 2) Add b to all words of length 1 --> 1 + 1 = 2)
13. Words of length 3: (Add aa to all words of length 1 --> 1 + 2 = 3) (Add b to all words of length 2 --> 2 + 1 = 3) aab baa bbb = 3 words Words of length 4: (Add b to all words of length 3) (Add aa to all words of length 2) baab bbaa bbbb aaaa aabb = 5 words
14. Words of length 6: (Add aa to the 5 words of length 4) (Add b to the 8 words of length 5) = 13 words This is the Fibonacci sequence: 1,2,3,5,8,13,…
15. • Consider the language S*, where S = {ab ba}. Write out all the words in S* that have seven or fewer letters. Can any word in this language contain the substrings aaa or bbb? What is the smallest word that is not in this language? Words of length 0: Λ Words of length 2: ab ba Words of length 4: abab abba baab baba Words of length 6: ababab ababba abbaab
16. • No words can contain aaa or bbb because the first a in string ab and the a in ba never allow to make aaa or bbb.
17. • Consider the language S*, where S = {xx xxx}. In how many ways can x 19 be written as the product of words in S? This means: How many different factorizations are there of x 19 into xx and xxx? Example: (xx) (xx) (xx) (xx) (xx) (xx) (xx) (xx) + (xxx) = x16+x3=x19
18. Cont’d… 3 doubles can be replaced by 2 triples: (xx) (xx)(xx) = (xxx)(xxx) Let xx = d and xxx = t • The number of ways of factoring 19 x’s into d’s and t’s is equal to: • The number of ways of arranging 8d’s and 1t + the number of ways of arranging 5 d’s and 3 t’s
19. (i) Let S = {ab bb} and let T = {ab, bb, bbbb}. Show that S* = T*. (ii) Let S = {ab, bb} and let T = {ab, bb, bbb}. Show that S* ≠ T*, but that S* ⊂ T* (i) S* = {Λ and all possible concatenations of ab and bb} T* = {Λ and all possible concatenations of ab, bb, and bbb}, but bbb is just bb concatenated with itself, so T* = {Λ and all concatenations of ab and bb}
20. • (ii) Let S = {ab, bb} and let T = {ab, bb, bbb}. Show that S* ≠ T*, but that S* ⊂ T* • The reason is that T contains triple b, and S contains double b. S* will always add double b, thus resulting string will be even only. However, S* ⊂ T*. Please evaluate S* and T* to prove above statement.