1. Lecture # 3 Theory Of Automata By Dr. MM Alam
2. Lecture#2 Recap • Kleene Closure • Examples of Kleene Closure. • Plus Operation
3. 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+}
4. 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*
5. (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+
6. (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*.
7. 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
8. 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
9. 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)
10. • Let us define (S**)* = S*** Is this set bigger than S*? Is it bigger than S? • S*** is no bigger than S*. Both sets contain an infinite number of elements. S*** is bigger than S (if S is not {Λ}) because it is made up of all concatenations of elements in S.
11. • (i) If S = {a b} and T* = S*, prove that T must contain S. (ii) Find another pair of sets S and T such that if T* = S*, then S ⊂ T (i) S* = {Λ and all concatenations of a’s and b’s} = T*. This means that a ∈ T and b ∈ T. (The smallest words in S* and T*). T may contain other strings (only
12. (ii) Find another pair of sets S and T such that if T* = S*, then S ⊂ T T = {a, b, aa, abb} S⊂T S = {a b aa} • Still S* = T* but S ⊂ T
13. Four different ways, in which a language can be defined • So far, we have studied many languages like INTEGER, PRIME, PALINDROME etc., • Now, we will take a detailed look at how a language can be defined in different ways. • There are four ways that we will study in this course: – Descriptive way – Recursive way – Regular Expression
14. Descriptive Definition of a Language • The language and its associated conditions are defined in plain English. • This way is semi-formal way with chances of ambiguity. • Descriptive method is used in early phases of requirement engineering and resultant equations are then formally transformed using other methods.
15. • Example: The language L of strings of even length, defined over Σ={b}, can be written as L={bb, bbbb, …..} • Example: The language L of strings that does not start with a, defined over Σ={a,b,c}, can be written as L={b, c, ba, bb, bc, ca, cb, cc, …}
16. • Example: The language L of strings of length 3, defined over Σ={0,1,2}, can be written as L={000, 012, 022,101, 101,120,…} • Example: The language L of strings ending in 1, defined over Σ ={0,1}, can be written as L={1,001,101,0001,0101,1001,1101,…}
17. • Example: The language EQUAL, of strings with number of a’s equal to number of b’s, defined over Σ={a,b}, can be written as {Λ ,ab,aabb,abab,baba,abba,…} • Example: The language EVEN-EVEN, of strings with even number of a’s and even number of b’s, defined over Σ={a,b}, can be written as {Λ, aa, bb, aaaa,aabb,abab, abba, baab,
18. • Example: The language INTEGER, of strings defined over Σ={-,0,1,2,3,4,5,6,7,8,9}, can be written as INTEGER = {…,-2,-1,0,1,2,…} • Example: The language EVEN, of stings defined over Σ={-,0,1,2,3,4,5,6,7,8,9}, can be written as EVEN = { …,-4,-2,0,2,4,…}
19. • Example: The language {anbn }, of strings defined over Σ={a,b}, as {an bn : n=1,2,3,…}, can be written as {ab, aabb, aaabbb,aaaabbbb,…} • Example: The language {anbncn }, of strings defined over Σ={a,b,c}, as {an bn cn: n=1,2,3,…}, can be written as {abc, aabbcc, aaabbbccc,aaaabbbbcccc,
20. Lecture#3 Summary • Plus Operation Examples • Four ways of defining languages • Examples for Descriptive way of defining languages