then
The strings in L 2 consist of one or more b’s. Therefore, we arrive at the
answer by removing one or more b’s from those strings in L 1 that terminate with
at least one b.
Note that here L 1 , L 2 , and L 1 /L 2 are all regular. This suggests that the right
quotient of any two regular languages is also regular. We will prove this in the
next theorem by a construction that takes the dfa's for L 1 and L 2 and constructs
from them a dfa for L 1 /L 2 . Before we describe the construction in full, let us see
how it applies to this example. We start with a dfa for L 1 ; say the automaton M 1
= (Q,Σ,δ,q 0 , F) in Figure 4.1. Since an automaton for L 1 /L 2 must accept any
prefix of strings in L 1 , we will try to modify M 1 so that it accepts x if there is any
y satisfying (4.1). The difficulty comes in finding whether there is some y such
that xy ∈ L 1 and y ∈ L 2 . To solve it, we determine, for each q ∈ Q, whether there
is a walk to a final state labeled υ such that υ ∈ L 2 . If this is so, any x such that
δ(q 0 , x)= q will be in L 1 /L 2 We modify the automaton accordingly to make q a
final state.
To apply this to our present case, we check each state q 0 ,q 1 , q 2 , q 3 , q 4 , q 5 to
see whether there is a walk labeled bb* to any of the q 1 , q 2 , or q 4 . We see that
only q 1 and q 2 qualify; q o , q 3 , q 4 do not. The resulting automaton for L 1 /L 2 is
shown in Figure 4.2. Check it to see that the construction works. The idea is
generalized in the next theorem.
Figure 4.1
The strings in L 2 consist of one or more b’s. Therefore, we arrive at the
answer by removing one or more b’s from those strings in L 1 that terminate with
at least one b.
Note that here L 1 , L 2 , and L 1 /L 2 are all regular. This suggests that the right
quotient of any two regular languages is also regular. We will prove this in the
next theorem by a construction that takes the dfa's for L 1 and L 2 and constructs
from them a dfa for L 1 /L 2 . Before we describe the construction in full, let us see
how it applies to this example. We start with a dfa for L 1 ; say the automaton M 1
= (Q,Σ,δ,q 0 , F) in Figure 4.1. Since an automaton for L 1 /L 2 must accept any
prefix of strings in L 1 , we will try to modify M 1 so that it accepts x if there is any
y satisfying (4.1). The difficulty comes in finding whether there is some y such
that xy ∈ L 1 and y ∈ L 2 . To solve it, we determine, for each q ∈ Q, whether there
is a walk to a final state labeled υ such that υ ∈ L 2 . If this is so, any x such that
δ(q 0 , x)= q will be in L 1 /L 2 We modify the automaton accordingly to make q a
final state.
To apply this to our present case, we check each state q 0 ,q 1 , q 2 , q 3 , q 4 , q 5 to
see whether there is a walk labeled bb* to any of the q 1 , q 2 , or q 4 . We see that
only q 1 and q 2 qualify; q o , q 3 , q 4 do not. The resulting automaton for L 1 /L 2 is
shown in Figure 4.2. Check it to see that the construction works. The idea is
generalized in the next theorem.
Figure 4.1