Construct a DFA for the following language: all strings that have at least three 0s and at most two 1s.

Question

Hello, I am to construct a DFA from the intersection of two simpler DFAs. The first simpler DFA recognizes languages of all strings that have at least three 0s, and the second simpler language DFA recognizes languages of strings of at most two 1s. The alphabet is (0,1). I'm not sure how to construct a larger DFA combining the two. Thanks!

Answer 1

Here's a general idea:

The most straightforward way to do this is to have different paths for counting your 0s that are based on the number of 1s you've seen, such that they are "parallel" to each other. Move from one layer of the path to the next any time you see a 1, and then move from the last layer to a trap state if you see a third 1. Depending on the exact nature of the assignment you might be able to condense this, but once you have a basic layout you can determine that. Typically you can combine states from the first DFA with states in the second DFA to produce a smaller end result.

Here's a more mathematical explanation:

Constructing automata for the intersection operation.
Assume we are given two DFA M1 = (S1, q(1) 0 , T1, F1) and M2 = (S2, q(2) 0 , T2, F2). These two DFA recognize languages L1 = L(M1) and L2 = L(M2). We want to design a DFA M= (S, q0, T, F) that recognizes the intersection L1 ∩L2. We use the idea of constructing the DFA for the union of languages. Given an input w, we run M1 and M2 on w simultaneously as we explained for the union operation. Once we finish the runs of M1 and of M2 on w, we look at the resulting end states of these two runs. If both end states are accepting then we accept w, otherwise we reject w.

---

When constructing the new transition function, the easy way to think of it is by using pairs of states. For example, consider the following DFAs:

Now, we can start combining these by traversing both DFAs at the same time. For example, both start at state 1. Now what happens if we see an a as input? Well, DFA1 will go from 1->2, and DFA2 will go from 1->3. When combining, then, we can say that the intersection will go from state "1,1" (both DFAs are in state 1) to state "2,3". State 2 is an accept state in DFA1 and state 3 is an accept state in DFA2, so state "2,3" is an accept state in our new DFA3. We can repeat this for all states/transitions and end up with:

Does that make sense?

Reference: Images found in this assignment from Cornell University.

Answer 2

The simplest way would be using the 2DFA model: from the end state of the first DFA(the one testing for at least 3 zeros) jump to the start state of the second one, and reverse to the beginning of the input. Then let the second DFA test the string.