Lecture 7Scribe Notes for ECS 20 (Prof. Rogaway) Scribe: Charles Hollister Today: 1. Back to Sets 2. Languages 3. Regular Languages Basic Set Operation: Recall the basic set operator, ∈. From this operator come other set quantifiers and operations: ⊆, ⊇ , , ∪ ∩\“Set difference” (sometimes denoted – , a minus sign) ⊕ - symmetric difference (xor for sets, denoted Δ in your book and sometimes denoted (circled v)) x – Cartesian product – A x B is the set of ordered pairs (a,b) with the 1st element in the first set and the 2nd element in the 2nd set P – Power set operator, unary operator (takes 1 input). P(x) is the “set of all subsets of x” P(X) = {A:A X} ⊆ More on power sets: For example, take X={0,1,2}, then P(x)={φ,{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}} We can more systematically enumerate the elements of this set by counting in binary just as in a truth table, indicating if the given element is (1) or is not (0) in the given set:“2” “1” “0” 0 0 0 φ 0 0 1 {0} 0 1 0 {1} 0 1 1 {0,1} 1 0 1 {0,2} 1 1 0 {1,2} 1 1 1 {0,1,2} (Aside - Prof. Rogaway mentioned in class that we should structure our truth tables by counting in binary in the usual order, like above, as good practice for readability and to be systematic) Notice in the table that the power set of X had 8 values in it. In general, if X is finite, then |P(X)| = 2|X| . Indeed sometimes P(X) is written 2X as a reminder of how big this set is. As another example, we talked abput P(N), where N is the set of natural numbers. Using the other set operators: Next, to help improve or facility with the operators on sets, we asked if the following claim is true or false: ?(\)\ \(\)AB C A BC= We can see from the diagram that the statement is false. Instead, based on inspection, it would appear that: (\)\ \( )ABC ABC=∪Proof: It is common to show set-equalities by arguing both inclulusions. But here we will do it all at once: ( \ )\ iff \ iff ( ) ( ) ( ) iff iff( ) iff ( ) iffx\( )xAB C x AB x CxA xB xC xA xB xCxA xBxC xA xBCABC∈∈∧∉∈∧∉∧∉ ∈∧¬∈∧¬∈∈∧¬∈∨∈ ∈∧¬∈∪∈∪ Set vocabulary definitions A few more words we often use: - singleton set – a set with only one element. - the empty set is the set with no elements. Denoted ∅. Note this symbol is not the same as a Greek letter phi. (Indeed I believe the origin is Norwegian). - We define |A| as the number of elements in A (or cardinality of A), also written n(A) and #A -Sets A and B are disjoint if A and B share no elements, ie, if their intersection is empty.. Classmate question – Does the “if” in the definition imply iff? Answer – yes, definitions always “iff” when “if” is used. Some formal language theory Σ- an alphabet – an alphabet is a finite, nonempty set. Eg, {0, 1}, {a, b}, {0,1,2,3,4,5,6,7,8,9}, {1}, ASCII – these are all alphabets. Elements in an alphabet are called characters (or sometimes symbols). - Is ∅ an alphabet? NO, it is empty. An alphabet must be nonempty. - is N, the set of natural numbers, an alphabet? No, it is infinite. An alphabet must be finite. A string is a finite sequence of characters. The characters all come from some understood alphabet. Examples and more definitions*Σrepresents all the strings over the alphabet Σ. This is an infinite set. But all the elements in this infinite set are strings of finite length. If {0,1}Σ= Then *{,0,1,00,01,10,11,000, ,111,0000,}εΣ= KL In this case,ε represents the “empty string”. It is the unique string of length 0. In the case of the English alphabet: {, ,}azΣ= K *Σcontains dog, fish,ε, etc Suppose x and y are strings, x, y ∈ Σ∗, - Then xyxy=o denotes the characters of x, in order, followed by the characters of y, again in order This is known as the concatenation operator; we have concatenated the two strings. Consider x = dog, y = fish, then xy = dogfish. - The symbols | … |, when applied to strings, as in x, denotes the length of the string x. So the symbol has a different meaning when applied to sets and strings. - True or False? A string exists of length ∞. False, strings are finite. - True or False? There exists a unique string of length 1. The answer depends upon the set. For , the unary alphabet, it’s true. For alphabets with 2 or more characters, it is false. {1}Σ= - The exponential operator in strings is defined as in 31111=, or more generally, xn = x xn-1 for n>0 and x0 = ε . - The reason we define the 0th power as the empty string, is so the last statement holds true for n=1, i.e. 1xxxε==o. - For the length operator, the following holds:xyxy=+. Clear?- x[i:j] is often used to represent substring of x starting at position I and ending at position j, where i ≥ 1, j ≤ |x|. For example, x=101101, 6; [2:5] 0110xx== RXis used to represent the “reversal” of X. (cat) tac, (hello) ollehRR== If Rxx= the we call x a palindrome. True or False – Palindromes are all of even length. False, consider “1”. 0 is both a character and a string: 0∈Σ εis only a string it is not a character. 01 is likewise a string, it is not a character. Language – A set of strings, all over the same alphabet. {0,1}Σ= This is a language. It is also an alphabet. All of the following are examples of languages: *{ ,00,01,10,11,0000,0001 } { : is even}Lxxε==∈L Σ {1 : p is prime} {11,111,11111,1111111, }PL == L *{ {0,1} : x represents a prime number, no leading zeroes, written in binary} ={10,11,101,111,1011}Lx=∈ L={dog, cat, fish} Languages can be finite or infinite. Languages are sets, so set operators apply to languages. For example:12121212{dog,cat,fish}{dog,frog}L4L\ 2L3LLLLL==∪==⊕= The concatenate function can be lifted to apply to language; when L1 and L2 are languages, L1 L2 is defined as all the combinations of a string from L1followed by a string from L2. That is, 12 1 2 1 2{| , }LLLL xyxLyL==∈∈o With the set we have written above, 12{dogdog,dogfrog,catdog,catfrog,fishdog,fishfrog}LL = True or False: ∅ is a language. True – all its elements are strings (that is, all 0 of them). L∅ = ∅ L =∅ {ε} is also a language – the singleton language containing just the empty string. Clearly {}LLε= as xxxεε== Student question:: is ε in every language?