Problem 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:
(a) 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 ∈ F (accepting state), return False (because L(M ) is not empty). 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 ) = ∅).
(b) 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).
3
Problem 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.
4
Problem 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:
(a) 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)∗.
(b) 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 for case 2:
b(a | b)(a | b)(b(a | b)(a | b))∗
Then we can combine both cases. So, the regexp is:
(a(a | b)(a | b)(a(a | b)(a | b))∗) | (b(a | b)(a | b)(b(a | b)(a | b))∗)
5
Problem 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.
6
Problem 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:
7
Problem 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, Σ, δ, q0, 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 (e.g., 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, Σ, δ, q0, 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 ∈ Q and a non-empty string w ∈ Σ+ such that:
δ(q, w) = q (meaning w forms a loop at state q)
There is a path from the start state q0 to q over some string u ∈ Σ∗.
There is a path from q to an accepting state in F over some string v ∈ Σ∗.
Using the identified cycle:
Set A1:
A1 = {uw2nv | n ≥ 0}
This set contains strings where the cycle w is traversed an even number of times.
Set A2:
A2 = {uw2n+1v | n ≥ 0}
This set contains strings where the cycle w is traversed an odd number of times.
Since n ≥ 0 can be any non-negative integer, and w is a non-empty string, both A1 and A2 contain
infinitely many strings by varying n.
Any string in A1 has the form uw2nv, where w is repeated an even number of times.
Any string in A2 has the form uw2n+1v, where w is repeated an odd number of times.
Since a number cannot be both even and odd simultaneously, the sets A1 and A2 are disjoint:
A1 ∩ A2 = ∅
We can write regular expressions representing A1 and A2 because regular languages are closed under
concatenation and Kleene star.
For A1:
u(ww)∗v
This expression concatenates u, zero or more repetitions of ww (even number of w), and v.
For A2:
u w (ww)∗v
This expression concatenates u, one w, zero or more repetitions of ww (maintaining an odd count), and
v.
Finite automata for A1 and A2:
We can construct finite automata M1 and M2 for A1 and A2, respectively, by modifying M :
For M1: Adjust the transitions to accept when the cycle w is traversed an even number of times.
For M2: Adjust the transitions to accept when the cycle w is traversed an odd number of times.
These automata are finite and recognize regular languages.
8
Union of A1 and A2:
A1 ∪ A2 = {uwnv | n ≥ 0} ⊆ A
Since u, w, and v are fixed strings and n ranges over all non-negative integers, A1 ∪ A2 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 A1 and A2
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 A1 and
A2.
9
Problem 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:
We will prove that ADD is not a regular language using the Pumping Lemma for regular languages.
Proof by Contradiction:
Suppose, for the sake of contradiction, that ADD is a regular language.
Then, by the Pumping Lemma for regular languages, there exists a pumping length p ≥ 1 such that
any string s ∈ ADD with length |s| ≥ p can be divided into three parts:
s = xyz
such that:
1. |y| ≥ 1
2. |xy| ≤ p
3. For all i ≥ 0, the string xyiz ∈ ADD
Now, consider the specific string s ∈ ADD defined as:
s = 1p
|{z}
x operand
+ 1p
|{z}
y operand
= 1 0p
|{z}
z (sum)
Here:
• x = 1p
• y = 1p
• z = 1 0p
This represents the binary addition:
(2p − 1) + (2p − 1) = 2p+1 − 2 = 2p × 2 − 2 = 2p(2 − 2
2p )
Simplifying, we get:
(2p − 1) + (2p − 1) = 2p+1 − 2
The length of s is:
|s| = |x| + 1 + |y| + 1 + |z| = p + 1 + p + 1 + (p + 1) = 3p + 3
Since p ≥ 1, |s| ≥ p.
According to the Pumping Lemma, since |xy| ≤ p, the substring y is entirely within the first operand 1p
(the initial sequence of 1’s). Thus, y consists only of 1’s from the first operand.
Let x, y, and z be divided as follows:
s = 1k
|{z}
x
1l
|{z}
y
1p−k−l + 1p = 1 0p
| {z }
z
where:
10
• k + l ≤ p
• l ≥ 1
Now, let’s pump y down by taking i = 0:
s′ = x y0 z = x z
So, s′ becomes:
s′ = 1k 1p−k−l + 1p = 1 0p
Simplifying the first operand:
1k+(p−k−l) = 1p−l
Thus, s′ represents the equation:
1p−l + 1p = 1 0p
In decimal, this is:
(2p−l − 1) + (2p − 1) = 2p+1 − 2
Simplify the left side:
(2p−l − 1) + (2p − 1) = 2p−l + 2p − 2
Simplify the right side remains 2p+1 − 2.
Subtract 2 from both sides:
2p−l + 2p − 2 = 2p+1 − 2
Cancel −2:
2p−l + 2p = 2p+1
Note that 2p+1 = 2 · 2p, so:
2p−l + 2p = 2 · 2p
Simplify left side:
2p−l + 2p = 2p−l + 2p
Simplify right side:
2p−l + 2p = 2p+1
Therefore:
2p−l + 2p = 2p+1 = 2p · 2
Subtract 2p from both sides:
2p−l = 2p(2 − 1) = 2p
So:
2p−l = 2p
11
This implies:
2p−l = 2p
Thus, we have:
p − l = p
Which simplifies to:
l = 0
But this contradicts the fact that |y| = l ≥ 1.
Conclusion:
We have reached a contradiction. The assumption that |y| ≥ 1 and l = 0 cannot both be true.
Therefore, our initial assumption that ADD is regular must be false.
Therefore, ADD is not a regular language.
12




Grade this. provide analysis and if anything is wrong let me know or if its right let me know too