On the boundary of regular languages

We prove that the tight bound on the state complexity of the boundary of regular languages, defined as bd(L)=L⁎∩(L¯)⁎, is 3/8⋅4n+2n−2−2⋅3n−2−n+23/8⋅4n+2n−2−2⋅3n−2−n+2. Our witness languages are described over a five-letter alphabet. Next, we show that this bound cannot be met by any quaternary language if n≥5n≥5. However, the state complexity of boundary in the quaternary case is smaller by just one. Finally, we prove that the state complexity of boundary in the binary and ternary cases is Θ(4n)Θ(4n).