CS 341 Homework 2Strings and Languages1. Let = {a, b}. Let L1 = {x *: |x| < 4}. Let L2 = {aa, aaa, aaaa}. List the elements in each of the following languages L: (a) L3 = L1 L2 (b) L4 = L1 L2 (c) L5 = L1 L4 (d) L6 = L1 - L22. Consider the language L = anbncm. Which of the following strings are in L? (a) (b) ab (c) c (d) aabc (e) aabbcc (f) abbcc3. It probably seems obvious to you that if you reverse a string, the character that was originally first becomes last. But the definition we've given doesn't say that; it says only that the character that was originally last becomes first. If we want to be able to use our intuition about what happens to the first character in a proof, we need to turn it into a theorem. Prove x,a where x is a string and a is a single character, (ax)R = xRa. 4. For each of the following binary functions, state whether or not it is (i) one-to-one, (ii) onto, (iii) idempotent, (iv) commutative, and (v) associative. Also (vi) state whether or not it has an identity, and, if so, what it is. Justify your answers. (a) || : S S S, where S is the set of strings of length 0 ||(a, b) = a || b (In other words, simply concatenation defined on strings) (b) || : L L L where L is a language over some alphabet ||(a, b) = {w *: w = x || y for some x a and y b} In other words, the concatenation of two languages A and B is the set of strings that can be derived by taking a string from A and then concatenating onto it a string from B.5. We can define a unary function F to be self-inverse iff x Domain(F) F(F(x)) = x. The Reverse function on strings is self-inverse, for example. (a) Give an example of a self-inverse function on the natural numbers, on sets, and on booleans. (b) Prove that the Reverse function on strings is self-inverse.Solutions1. First we observe that L1 = {, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb}. (a) L3 = {, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa} (b) L4 = {aa, aaa} (c) L5 = every way of selecting one element from L1 followed by one element from L4:{aa, aaa, baa, aaaa, abaa, baaa, bbaa, aaaaa, aabaa, abaaa, abbaa, baaaa, babaa, bbaaa, bbbaa} {aaa, aaaa, baaa, aaaaa, abaaa, baaaa, bbaaa, aaaaaa, aabaaa, abaaaa, abbaaa, baaaaa, babaaa, bbaaaa, bbbaaa}. Note that we've written aa, just to make it clear how this string was derived. It should actually be written as just aa. Also note that some elements are in both of these sets (i.e., there's more than one way to derive them). Eliminating duplicates (since L is a set and thus does not contain duplicates), we get:{aa, aaa, baa, aaaa, abaa, baaa, bbaa, aaaaa, aabaa, abaaa, abbaa, baaaa, babaa, bbaaa, bbbaa, aaaaaa, aabaaa, abaaaa, abbaaa, baaaaa, babaaa, bbaaaa, bbbaaa} (d) L6 = every string that is in L1 but not in L2: {, a, b, ab, ba, bb, aab, aba, abb, baa, bab, bba, bbb}.2. (a) Yes. n = 0 and m = 0. (b) Yes. n = 1 and m = 0. (c) Yes. n = 0 and m = 1. (d) No. There must be equal numbers of a's and b's.Homework 2 Strings and Languages 1(e) Yes. n = 2 and m = 2. (f) No. There must be equal numbers of a's and b's.3. Prove: x,a where x is a string and a is a single character, (ax)R = xRa. We'll use induction on the length of x. If |x| = 0 (i.e, x = ), then (a)R = a = Ra. Next we show that if this is true for all strings of length n, then it is true for all strings of length n + 1. Consider any string x of length n + 1. Since |x| > 0, we can rewrite x as yb forsome single character b. (ax)R = (ayb)RRewrite of x as yb = b(ay)RDefinition of reversal= b(yRa) Induction hypothesis (since |x| = n + 1, |y| = n)= (b yR) a Associativity of concatenation= xRa Definition of reversal: If x = yb then xR = byR4. (a) (i) || is not one-to-one. For example, ||(ab, c) = ||(a, bc) = abc. (ii) || is onto. Proof: s S, ||(s, ) = s, so every element of s can be generated.(iii) || is not idempotent. ||(a, a) a.(iv) || is not commutative. ||(ab, cd) (cd, ab)(v) || is associative. (vi) || has as both a left and right identity. (b) (i) || is not one to one. For example, Let = {a, b, c}. ||({a}, {bc}) = {abc} = ||({ab}, {c})(ii) || is onto. Proof: L *, ||(L, {}) = L, so every element of s can be generated. Notice that this proof is very similar to the one we used to show that concatenation of strings is onto. Both proofs rely onthe fact that is an identity for concatenation of strings. Given the way in which we defined concatenation of languages as the concatenation of strings drawn from the two languages, {} is an identity for concatenation of languages and thus it enables us to prove that all languages can be derived from the concatenation operation. (iii) || is not idempotent. ||({a}, {a}) = {aa}(iv) || is not commutative. ||({a}, {b}) = {ab}. But ||({b}, {a}) = {ba}.(v) || is associative.(vi) || has {} as both a left and right identity.5. (a) Integers: F(x) = -x is self-inverse. Sets: Complement is self-inverse. Booleans: Not is self-inverse. (b) We'll prove this by induction on the length of the string. Base case: If |x| = 0 or 1, then xR = x. So (xR)R = xR = x.Show that if this is true for all strings of length n, then it is true for all strings of length n + 1. Any string s of length n + 1 can be rewritten as xa for some single character a. So now we have:sR = a xRdefinition of string reversal(sR)R = (a xR)Rsubstituting a xR for sR= (xR)Ra by the theorem we proved above in (3)= xa induction hypothesis= s since xa was just a way of rewriting sHomework 2 Strings and Languages
View Full Document
Unlocking...