Let Σ = {0, 1} and let D = {w | w contains an equal number of occurances of the
substrings 01 and 10}. Thus 101 ∈ D because it contains a single 01 and a single 10
but 1010 ̸∈ D because it contains a single 01 but two 10s. Show that D is a regular
Language.

Answer: Proof by contradiction using the pumping lemma. It is not regular.

Assume for contradiction that D is a regular language.
According to the pumping lemma, there exists a pumping length p such that any string s in D with |s| >= p can be decomposed into three parts s = xyz satisfying: |xy| <= p, |y| > 0, for all i >= 0, the string xy^(i)z must also be in D.
I will choose a specific string s EPSILON D (|s| >= p). My choice is s = 01^(p)0, this string has one occurrence of 01 and one occurrence of 10. 
We can write s = xyz such that |xy| <= p and |y| > 0. Since |xy| <= p, both x and y must consist of only 0s and 1s from the prefix 01^p. Thus, y will consist solely of 1s. Let y = 1^k for some k > 0.
Now we consider the string xy^(2)z: xy^(2)z = x1^(2k)z. This string has the same single occurrence of 01 at the beginning and no occurrences of 10 because the segment 0 is not adjacent to the first 1. Hence the pumped string xy^2z contains one occurrence of 01 but no occurrences of 10. 
Since xy^2z is not in D, we reach a contradiction with D being regular. So, D is not a regular language. 


2.  (Let Σ = {0, 1} and let Bsubscript3 = {w | w is a proper binary representation of a number divisible by 3}, where “proper” means the representation has no leading 0s unless the entire string is just one zero. Is Bsubscript3 a regular language?

Answer: Yes, it is regular.

To start: the strings can’t have leading zeroes. A binary number is divisible by 3 based on the modulo 3 remainder of its value. We can construct a DFA that represents the reminders (0, 1, and 2) when divided by 3. The accepting state only accepts when the remainder is 0, or the input is divisible by 3. Since we can construct a DFA (shown below) for the language, we can conclude that it is regular.
















3. In this problem, assume that the components of a DFA are given to you in appropriate data structures, that is, sets for Q, Σ, and F and a map (dictionary) for δ. 

(a) Describe a method, i.e. an algorithm, which, given a DFA M = (Q, Σ, δ, q0, F), determines whether L(M) = ∅. 
(b) Describe a method, i.e. an algorithm, which, given two DFAs M1 and M2, determines whether their languages are disjoint, that is, whether L(M1) ∩ L(M2) = ∅.

Answers:

I am not the greatest at pseudocode, so I am going to just describe this algorithm in English to the best of my ability. First, we make an empty set - let’s call it “visited” - to keep track of states that have been visited. Then we create a stack and push the initial state q0. While the stack is not empty, we pop a state q from the stack. Then, if q is in F (accepting state) return False (because L(M) is not ∅y). If q is not in visited, add q to visited, then for each symbol a∈Σ, we compute the next state q’ = δ(q,a). If q’ is not in visited, we push q’ onto the stack. If the loop ends and no accepting state has been reached, we return true (indicating that L(M) = ∅.)
Here we are determining whether the languages recognized by two DFAs are disjoint. First, we can make a new DFA that tracks the states of both DFAs at the same time. The new DFA starts in a state where both DFA 1 and DFA 2 are in their starting states. For every character we read, we move both DFAs according to their own rules. The new machine is accepting if both DFAs are in accepting states. If we can reach any accepting state in this combined machine, it means at least one string is accepted by both DFA 1 and 2, meaning they aren’t disjoint. We would then need to check all states that we can reach in this new DFA, and keep track of visited states. If we find a state that accepts for our new DFA, L(M1​)∩L(M2​)=∅ (the languages are not disjoint). If none exist, L(M1​)∩L(M2​)=∅ (the languages are disjoint).

4. Suppose L1 and L2 are both regular languages and that L2 ⊆ L1. Show that the language L3 = {w | w ∈ L1 but w ̸∈ L2} is regular.

Answer: Yes, it is regular.

As previously mentioned in the textbook, regular languages can be expressed using regex, finite automata, or grammars.  L3 has all strings that are in L1 but not L2. Since L2 is regular, we can make a language that includes all the strings that are NOT in L2. This new language is also regular because taking the complement keeps a language regular. Now we can take the strings in L1 and check them against our new language - the complement of L2. When we combine L1 with the complement of L2 (finding strings that are both in L1 and not in L2) we are performing an intersection. Since both L1 and the complement of L2 are regular languages, their intersection is also a regular language. Again, taking the union, finding the intersection, and taking the complement keep languages regular if they’re already regular - they’re closed under those operations.






5. In this problem, Σ = {a, b}. For each of the following languages, give three examples of strings in the language and find a regular expression for the language. (a) L1 = {w | |w| is a multiple of 3} (b) L2 = {w | |w| ≥ 3 and |w| is a multiple of 3 and (if w is long enough) the 4th, 7th, and every third letter after the 7th letter of w is the same as the first letter } (So, e.g., abbaababaabb ∈ L2)

Answer: 
Three examples could be aaa (length 3), bbb (length 3), and abbbaa (length 6). To form a regular expression for this language we need a group of 3 symbols repeated any number of times. It could be either a or b for any of these. So the regular expression could be (a|b)(a|b)(a|b)*. I think we could also shorten this to (a|b)^3*. 
This language has strings that are a multiple of 3 like the last one, but also at least 3 characters in the string, and if it is at least 7 characters long then the 4th, 7th, and every 3rd letter after the 7th must match the first letter of the string. Some examples could be aaa (length 3), aaabbb (length 6), and abbbaa (length 6). Regular expressions can’t really remember characters, but we only have two possible characters, so we can split the regex into two cases. Case 1 is that the first letter is a, and case 2 is that the first letter is b. For case 1: a (a|b)(a|b) (a (a|b)(a|b))*, and case 2: b (a|b)(a|b) (b a|b)(a|b))*. Then we can combine both cases. So, the regexp for b is:					 ( a(a|b)(a|b)( a(a|b)(a|b))* | ( b(a|b)(a|b)( b (a|b)(a|b))* )

fact check my answers. if any are wrong, provide the correct answer instead. thank you!