We study maximal prefix-free subsets of regular languages and their descriptional complexity. We start with finite subsets and give the constructions of deterministic finite automata for largest and smallest finite maximal prefix-free subsets. Then we consider infinite maximal prefix-free subsets, and we show that such subsets can be effectively found if they exist. Finally, we prove that if a regular language has a non-regular maximal prefix-free subset, then it has uncountably many maximal prefix-free subsets.
展开▼
