quote
COT-5310 Theory of Computation I Assignment 1 Florida International University School of Computing and Information Sciences 1. (10 points) Let A and B be two sets such that |A| = m, |B| = n and |A\B| = k. Find the cardinality of the following sets as a function of m, n, and k: (a) P(A×B) (b) (A ∪B)3 (c) A2 ∪B2 2. (10 points) Using formal proof methods, prove or disprove the following claims: (a) Let R be a binary relation on set A. Assuming that R is reflexive and symmetric, ∀x, y ∈ A, xRy iff {z ∈ A|xRz} = {z ∈ A|yRz}. (b) Let R be a binary relation on set A. Assuming that R is an equivalence relation, ∀x, y ∈ A, xRy iff {z ∈ A|xRz} = {z ∈ A|yRz}. 3. (25 points) Let L1 = {w ∈ {a, b}∗| 2|na(w)} where na(w) represents the number of occurrences of letter a in string w and L2 = {w ∈ {a, b}∗| aab is a substring of w}. (a) Draw a DFA that recognizes L1. (b) Draw a DFA that recognizes L2. (c) Draw a DFA that recognizes L2\L1. 4. (15 points) Consider the following DFA: s0start s1 s2 1 0 1 0 1 0 1 (a) Describe the language recognized by this DFA. (b) Write down the 5-tuple representing this DFA. 5. (15 points) Draw a DFA that recognizes the octal representation of all non-negative integers divisible by 3. Obviously, the alphabet is Σ = {0, 1, 2, . . . , 7} and the language recognized by the DFA should look like this: {0, 3, 6, 00, 03, 06, 11, 14, 17, 22, 25, 30, 33, 36, . . .} (Hint: you don’t need more than three states to make this DFA). 6. (15 points) Draw a DFA that recognizes the following language: {w ∈ {0, 1}∗| 011 is a not postfix of w ∨ |w| is odd} 7. (10 points) Let’s accept (without proof) that the set of all regular languages over an arbitrary alphabet Σ is closed under union, intersection and star operations. Given regular languages L1 and L2, prove that the following languages are regular as well: (a) L1\L∗2 (b) L1∆L2 2