Let Σ = {0, 1} and let D = {w | w contains an equal number of occurrences 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: Every time the input switches from 0 to 1, we have 01. Every time it switches from 1 to 0, we have 10. So, the number of 01 and 10 substrings can differ by most by 1. If a string starts with 0 and ends with 0 or starts with 1 and ends with 1, the counts of 01 and 10 substrings are equal. If a string starts with 0 and ends with 1 or starts with 1 and ends with 0, the counts differ by 1. D includes only strings where the counts are equal. So, we can construct a DFA that keeps track of the current symbol (0 or 1) and the parity of the counts of 01 and 10 substrings. 

Our states can be even, odd, start0, and start1. We start in even either way. Then, when reading a symbol that does not change from the previous symbol, stay in the current state. On reading a symbol that changes from the previous symbol, if moving from even then go to odd. If going from odd then go to even.The DFA accepts when we end in even.

Since we can make a DFA to recognize D, D is 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))* )

6. Let L ⊆ Σ∗ and define P(L), the prefix-language of L, as
P(L) = {w ∈ Σ∗| x = wy for some x ∈ L, y ∈ Σ∗}
Show that if L is regular, then P(L) is also regular.

Answer:roblem 6
Let L ⊆ Σ∗ and define P (L), the prefix-language of L, as
P (L) = {w ∈ Σ∗ | x = wy for some x ∈ L, y ∈ Σ∗}
Show that if L is regular, then P (L) is also regular.
Answer:
If L is a regular language, then its prefix language P (L) is also regular.
Proof:
Since L is regular, there exists a deterministic finite automaton (DFA) M = (Q, Σ, δ, q0, F ) that recognizes
L.
To construct a DFA M ′ that recognizes P (L):
1. Use the same states and transitions as M : - M ′ = (Q, Σ, δ, q0, F ′). - The start state q0 and
transition function δ remain unchanged.
2. Define the new set of accepting states F ′: - F ′ consists of all states that can reach an accepting
state in M :
F ′ = {q ∈ Q | There exists a path from q to some f ∈ F }
- These are states from which some continuation leads to acceptance in M .
The DFA M ′ accepts exactly those strings that are prefixes of strings in L:
- For any w ∈ P (L), there exists y such that wy ∈ L. - In M ′, reading w leads to a state q ∈ F ′ because
q can reach an accepting state in M via some y. - Conversely, if M ′ accepts w, then there is a path from q0
to some q ∈ F ′ reading w, and since q can reach an accepting state in M , there exists y such that wy ∈ L.
Conclusion:
Since M ′ is a DFA recognizing P (L), and regular languages are closed under DFA recognition, P (L) is
regular.










7. Let Σ = {a, b}.
(a) Find a simple nondeterministic finite automaton accepting (a ∪ b)
∗aab.
(b) Convert the NFA of part (a) to a DFA by the method in Sipser. Provide only the
portion of the DFA that’s reachable from the start state.

Here is the NFA:












Here is the DFA:






















8. Let A be an infinite regular language. Show that A can be split into two infinite disjoint regular subsets. 

Answer: 

Since A is a regular language, there exists a DFA (M = (Q, Sigma, delta, q_0, F)), that recognizes A. Since A is infinite but the DFA has finitely many states, by the pigeonhole principle, there must be cycles in M. Specifically, there is at least one loop on some path from the start state to an accepting state in F. We can use this cycle to generate infinitely many accepted strings by traversing the loop multiple times. So, we can define two subsets (A1) and (A2) based on the number of times the loop is traversed (eg, even vs odd). So, we need to show that A1 and A2 are infinite, disjoint, and regular. This proof is a bit long, so I apologize if it’s not very concise.

Let’s consider the minimal DFA ( M = (Q, Sigma, delta, q_0, F) ) that recognizes the infinite regular language ( A ). Since ( A ) is infinite and ( M ) has a finite number of states, there must be at least one cycle in ( M ).


There exists a state ( q \in Q ) and a non-empty string ( w \in \Sigma^+ ) such that:
( \delta(q, w) = q ) (meaning ( w ) forms a loop at state ( q )).
There is a path from the start state ( q_0 ) to ( q ) over some string ( u \in \Sigma^* ).
There is a path from ( q ) to an accepting state in ( F ) over some string ( v \in \Sigma^* ).

Using the identified cycle:
Set ( A_1 ):
[
A_1 = { uw^{2n}v \mid n \geq 0 }
]
This set contains strings where the cycle ( w ) is traversed an even number of times.
Set ( A_2 ):
[
A_2 = { uw^{2n+1}v \mid n \geq 0 }
]
This set contains strings where the cycle ( w ) is traversed an odd number of times.


Since ( n \geq 0 ) can be any non-negative integer, and ( w ) is a non-empty string, both ( A_1 ) and ( A_2 ) contain infinitely many strings.
By varying ( n ), we get infinitely many different strings in each set due to the repetition of ( w ).


Any string in ( A_1 ) has the form ( uw^{2n}v ), where ( w ) is repeated an even number of times.
Any string in ( A_2 ) has the form ( uw^{2n+1}v ), where ( w ) is repeated an odd number of times.
Since a number cannot be both even and odd simultaneously, the sets ( A_1 ) and ( A_2 ) are disjoint:
[
A_1 \cap A_2 = \emptyset
]


We can write regular expressions representing ( A_1 ) and ( A_2 ) because regular languages are closed under concatenation and Kleene star.
For ( A_1 ):
[
u(w w)^* v
]
This expression concatenates ( u ), zero or more repetitions of ( w w ) (even number of ( w )), and ( v ).
For ( A_2 ):
[
u w (w w)^* v
]
This expression concatenates ( u ), one ( w ), zero or more repetitions of ( w w ) (maintaining an odd count), and ( v ).
Finite Automata for ( A_1 ) and ( A_2 ):
We can construct finite automata ( M_1 ) and ( M_2 ) for ( A_1 ) and ( A_2 ), respectively, by modifying ( M ):
For ( M_1 ): Adjust the transitions to accept when the cycle ( w ) is traversed an even number of times.
For ( M_2 ): Adjust the transitions to accept when the cycle ( w ) is traversed an odd number of times.
These automata are finite and recognize regular languages.


Union of ( A_1 ) and ( A_2 ):
[
A_1 \cup A_2 = { uw^{n} v \mid n \geq 0 } \subseteq A
]
Since ( u ), ( w ), and ( v ) are fixed strings and ( n ) ranges over all non-negative integers, ( A_1 \cup A_2 ) comprises all strings formed by traversing the cycle any number of times, which are in ( A ).
Note that there may be other strings in ( A ) not of this form; however, since ( A ) is infinite, and ( A_1 ) and ( A_2 ) are infinite subsets of ( A ), we have effectively split ( A ) into two infinite disjoint regular subsets.
Therefore, any infinite regular language ( A ) can be split into two infinite disjoint regular subsets ( A_1 ) and ( A_2 ).


9. Let Σ = {0, 1, +, =} and
ADD = {x + y = z | x, y, z are binary integers, and z is the sum of x and y}.
Show that ADD is not regular.

Answer: I’m going to prove this by contradiction. Let’s assume ADD is a regular language. Since ADD is regular, there exists a pumping length such that any string in ADD with |s| \geq p can be divided into three parts (s = xyz) satisfying:
|xy| \leq p
|y| \geq 1
For all (i \geq 0), (x y^i z \in \text{ADD})

Let ( s = 1^p + 1 = 1 0^p ).
( x = \underbrace{1^p}_{\text{first operand}} )
The '+' and '=' symbols are part of the fixed format.
( y = 1 ) (the second operand, which is just '1')
( z = 1 0^p ) (the sum, representing ( 2^p ))
Since ( |xy| \leq p ) and ( |y| \geq 1 ), the string ( y ) must consist of at least one '1' from the first operand.
So ( y ) is a substring of the initial sequence of '1's.
Remove ( y ) to get ( s' = x z ).
The new first operand becomes ( 1^{p - |y|} ).
The rest of ( s ) remains unchanged.
Original equation: ( 1^p + 1 = 1 0^p ) represents ( (2^p - 1) + 1 = 2^p ).
Pumped-down equation: ( 1^{p - |y|} + 1 = 1 0^p ) represents ( (2^{p - |y|} - 1) + 1 = 2^p ).
Simplifies to ( 2^{p - |y|} = 2^p ), which is false unless ( |y| = 0 ), but ( |y| \geq 1 ).
Therefore, ( s' \notin \text{ADD} ), which contradicts the pumping lemma.
The assumption that ADD is regular must be false.
Hence, ADD is not a regular language.







Grade this exam. Is there anything incorrect? Or is it a 100? Thanks!