University:
California State University, Northridge
Course:
COMP 310 | Automata, Languages and Computation
Academic year:

2024
Views:

488

Pages:

2
Author:

Samuel K.

COMP 310 Quiz 1: Name NOGA Problem 1. (10 points) Assume X = {a,c,f}, Y = {b,e,d}, Z = {a,b,c,d}, and U = {a,b,c,d,e,f}. Find each of the following sets. Z ∪ (Y ∩ X) = {a,b,c,d,e,f} Y Δ Z = {a} (X ∩ Z) x (Y ∩ X) = {(a,c), (c,c)} Y Δ (Z \ X) = {b,e} Problem 2. (10 points) Let R = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (3,5), (3,6), (4,1), (4,4), (5,3), (5,5), (5,6)} be a relation on {1,2,3,4,5,6}. State whether R has or doesn't have each of the following properties and briefly explain why. Reflexive: True ((1,1), (2,2), ..., (6,6)) Symmetric: No ((3,6) √ (6,3)) Transitive: No ((2,1), (1,4) ⇒ (2,4)) Anti-symmetric: No ((1,2), (2,1)) Problem 3. (10 points) Alicia had a string w consisting of N a's, followed by N b's, followed by N c's (in other words w = a^N b^N c^N). She selected a (consecutive) substring from w of length k where 1 ≤ k ≤ N. How many different types of letters could Alicia's substring contain. Since there are only 3 types of letters, your answer must be a subset of {0, 1, 2, 3}. Briefly justify (prove) your answer. 0 not possible 1 possible eg substring a OR b OR c 2 possible eg substring ab OR bc ... 3 not possible k ≤ N so can't contain all three way from a's through all N b's and continue into c's