Regular Languages meet Prefix Sorting