| Popis: |
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 ? 4 n + 2 n - 2 - 2 ? 3 n - 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 ? 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 ? ( 4 n ) . |
Full Text from ScienceDirect