Semi-flower languages are those of the form L* for some finite maximal prefix code L, or equivalently, those recognizable by a so-called semi-flower automaton, in which all the cycles have a common state qo, which happens to be the initial state and the only accepting state. We show that the syntactic complexity of these languages is exactly n~n — n! + n (where n stands for the state complexity as usual) and that this bound is reachable with an alphabet of size n.
展开▼
