1 From last time
A DFA is a simple machine that reads a string, one character at a time, and moves from state to state with each character. Formally, we define it with
• an input alphabet Σ
• a set of states Q
• astartstates∈Q
• asetofacceptstatesF ⊆Q
• atransitionfunctionδ:Q×Σ→Q Usually we just draw a diagram:
q1
0
q3
0
1
0
1
q2
1
q4 0,1
So here, for example, Σ = {0,1},Q = {q1,q2,q3,q4},s = q1,F = {q2,q4}, and I’m not gonna write out the whole δ but δ(q1, 1) = q2 and δ(q4, 0) = q4.
We use δˆ : Q × Σ∗ → Q for the multi-step transition function. We define it recursively based on δ: δˆ(q, λ) = q (if you read the empty string, don’t move) and for x ∈ Σ∗,y ∈ Σ,δˆ(q,xy) = δ(δˆ(q,x),y).
A DFA D accepts a string x if δˆ(s, x) ∈ F (that is, if reading x in the start state takes D to an accept state), and rejects x if not. The language of D, which we write L(D), is the set of strings accepted by D.
2 A More Complicated Example
Last time you saw an example DFA for the language {x ∈ {a, b}∗ | x contains 3 consecutive a}. Today we’re going to do {x ∈ {0, 1, 2}∗ | x is a ternary representation of an even number}.
1
(This is slightly different from the example in the book, because more examples is good.)
So we want the states of the machine to track if the number we’ve seen so far is even or odd. That means we need 2 states even, odd.
even
odd
What happens when we read a new digit in ternary? We shift everything we’ve read so far to the left, which is the same as multiplying by 3. Then we add the value of the new digit. An even number times 3 is even. Add 0 or 2 to an even number, and you get an even number. So δ(even, 0) = even.
even
odd
0,2
We can fill in the other transitions with the same logic:
1
even
odd
1
0,2 0,2
We want to accept if the string ends in the even state. Where do we start? If we read just the string 1, then we should be in the odd state; if we read 0 we should be in even. So even should be the start state. (Also we’re going to define λ as a representation of 0. If we didn’t do that, we’d need an extra state.)
1
even
odd
1
0,2 0,2
3 Closure Properties
Closure properties are general statements about what operations you can do on regular languages and have them still be regular. Let me do an example first:
2
Theorem 1. If L is regular, then ∼ L is regular.
What does this mean?
We know L = {x ∈ {0, 1, 2}∗ | x is a ternary representation of an even number} is regular. This says ”the set of everything not in L is also regular”. In other words, we know {x ∈ {0, 1, 2}∗ | x is a ternary representation of an odd number}
is regular, without having to construct a DFA for it.
How do we prove that theorem?
L is regular, so we can make a DFA for it. We need to show that if you can make a DFA for a language, then you can make a DFA for the opposite of the language. We need to do this in a very general way, though – we can’t assume anything about the DFA beyond ”it’s a DFA”.
But, we know that every DFA has a set of accept states. If the string ends in an accept state, it’s accepted, and if not, it’s rejected. So to reject all the accepted strings, we need to make all accept states not accept. To accept all the rejected strings, we need to make all the non-accept states accept. Let’s put that more formally:
Proof. If L is regular, there’s a DFA D = ⟨Q,Σ,s,F,δ⟩ that recognizes L. Construct a new DFA D′ = ⟨Q,Σ,s,Q−F,δ⟩. Suppose x ∈ L. Then D accepts the string x. Then there is some q ∈ F where δˆ(s,x) = q. Since q ̸∈ Q−F, D′ rejectsx. Similarly,ifx̸∈L,Drejectsx,soδˆ(s,x)̸∈F,soδˆ(s,x)∈Q−F,so D′ accepts x. Therefore, D′ is a DFA for ∼ L.
One nice thing about regular languages is they have lots of closure properties. Theorem 2. If A ⊂ Σ∗ and B ⊂ Σ∗ are regular, then the following languages
are also regular:
• A ∪ B (union)
• A ∩ B (intersection) • AB (concatenation) • ∼ A (complement)
• A∗ (asterate)
We’ll go over the proof for intersection. To do intersection, we need to combine two DFAs into one. The challenge is, we can still only read the string once, so we can’t do something like ”if you’re in the final state of the first DFA, go to the start state of the second DFA”. We need to run both DFAs at once. What we’re going to do is make a DFA where each state matches a pair of states. Let’s look at an example: we’ll combine the DFA for ”ternary even number” with the DFA for ”ternary multiple of 3”. Here’s the two DFAs:
3
10
even odd 0 1 1
1
0,2 0,2
0
1 02
1 2
2
2
We have to have a single start state. We’ll call that state ⟨even, 0⟩.
even, 0
Now, if we see a 0, the first machine goes from even to even and the second
goes from 0 to 0. So 0 should be a self-loop:
even, 0 0
On a 1, the first machine goes from even to odd, and the second goes from 0 to 1:
even,0
1
odd, 1
0
I recommend you fill in the rest! I put a complete version on the last page for you to compare with. Now here’s the formal definition of this construction and the proof that it works. The main thing to pay attention to is the type-checking.
Proof for intersection. Suppose A and B are regular, with DFAs DA = ⟨QA, Σ, sA, FA, δA⟩ andDB =⟨QB,Σ,sB,FB,δB⟩. ConstructaDFAD′ =⟨QA×QB,Σ,⟨sA,sB⟩,FA×
FB,δ′⟩ where δ′(⟨qa,qb⟩,x) = ⟨δ(qa,x),δ(qb,x)⟩.
4
Next step is to show that the transition function does what it’s supposed to. That is, δˆ′(⟨a, b⟩, x) = ⟨δˆ(a, x), δˆ(b, x)⟩. We’ll use induction on the length of x.
Base case: For x of length 1 and any state q, δˆ(q, x) = δ(q, x) and δˆ′(q, x) = δ′(q,x), so this is true from our definition of δ′.
Suppose it’s true for strings x of length ≤ n. Take a length n + 1 string yx (where y is a single symbol in Σ).
δˆ′(⟨qa, qb⟩, yx) = δˆ′(δ′(⟨qa, qb⟩, y), x)
= δˆ′(⟨δ(qa, y), δ(qb, y)⟩, x)
= ⟨δˆ(qa, yx), δˆ(b, yx)⟩
The first line is using the recursive definition of δˆ′. The second line is using the definition of δ′. The third line uses the inductive hypothesis.
Ok, so the transition function does what we want. Now, take a string x ∈ A∩B. That means x ∈ A, so δˆA(sA,x) ∈ FA, and x ∈ B, so δˆB(sB,x) ∈ FB. By the induction we just did, δˆ′(⟨sA,sB⟩) ∈ FA × FB, so our DFA D′ accepts x. By a similar argument, if x ̸∈ A ∩ B, then D′ rejects it. Therefore, D′ is a DFA for A ∩ B.
Bonus things to think about: how would you do this for union? How can you do union with just the closure properties we’ve proved?
5
2 0
even, 1 even, 2 02
11 11 11
0 odd, 1 2 odd,2
2
0
even, 0
odd,0
2
02 0
(You can make a simpler DFA – it’s possible to combine states 1 and 2 in the DFA for ternary multiple of 3, because that really just cares if the last character was a 0. That gets you down to 4 states here.)
6