CS341 Automata TheoryHomework Assignment ♯1Do not forget to write your name and EID at t he top of the first page of your solutionset. No collaboration is allowed; all solutions submitted must be your own work. Solutionsets must be stapled together.1. For each of the languages below, describe them very precisely and succintly in English.In addition to your precise English definition, list 8 strings that are in the language.(a) {xyz|x, y, z ∈ {a, b}∗, |x| = |z| and #a(x) ≥ #a(z)}(b) {a1a2...a2n∈ {0, 1}∗|n ≥ 1, a1a2...an∈ L, ai∈ L for all i}. Describ e this languageassuming that L = {0n|n ≥ 0}(c) {xaxR|x ∈ {a, b, c}∗}.2. Define a relation R on N × N (where N is the set of natural numbers) byR = {(x, y)|x ∈ N, y ∈ N and x+y is even}. Prove or disprove that R is an equivalencerelation.3. Write each of the following explicitly.(a) {1} × {1, 2} × {1, 2, 3}.(b) ∅ × {1, 2}.(c) 2{1,2}× {1, 2}.4. For each of the following statements, state whether it is True or False. Prove youranswer.(a) L1= L2if and only if L1∗= L2∗.(b) (∅ ∪ ∅∗) ∩ (∅ − (∅∅∗)) = ∅.(c) Every infinite language is the complement of a finite language.5. Let C be a set of sets defined as follows.(i) ∅ ∈ C.(ii) If S1∈ C and S2∈ C, then {S1, S2} ∈ C.(iii) If S1∈ C and S2∈ C, then S1× S2∈ C.(iv) Nothing is in C except that which follows from (i), (ii), and (iii).(a) Explain carefully why it is a consequence of (i) through (iv) that {∅, {∅}} ∈ C.(b) Give an example o f a set S of ordered pairs such that S ∈ C a nd |S| > 1.16. Show each of the following.(a) {ε}∗= {ε}.(b) For any language L, ∅L = L∅ = ∅.(c) ∅∗= {ε}.(d) L∗= L+if and only if ε ∈ L.7. Are the following sets closed under the given operations? Explain.(a) The negative integers under multiplication.(b) The positive integers under division.(c) The set of all strings over Σ under concatenation.8. Give examples to show that the intersection of two countably infinite sets can be eitherfinite or countably infinite, and that the intersection of two uncountable sets can befinite, countably infinite, or uncountable.9. Prove t hat given any sets A, B, and C, A − (B ∪ C) = (A − B) ∩ (A − C).10. Show that the set of real numbers between 0 and 1 (inclusive) is uncountable.11. Prove: The difference of an even number and an odd number is odd.12. Prove or disprove: If x 6 |(m − n) then x 6 |m or x 6
View Full Document
Unlocking...