Article ID Journal Published Year Pages File Type
435988 Theoretical Computer Science 2015 16 Pages PDF
Abstract

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).

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,