Skip to main content
3 of 3
broken link fixed, cf. https://math.meta.stackexchange.com/a/34713/228959
Glorfindel
  • 2.8k
  • 6
  • 28
  • 38

Yuval Filmus shows in Link that it is decidable for a regular language $L$ whether $w\in L\implies w^k\in L$ for all $k>0$. I would guess there must be an older reference. On the other hand, a language $L$ is called pure if $w^k\in L\implies w\in L$. It was shown by Pedro Silva that purity is decidable for regular languages in http://cmup.fc.up.pt/cmup/preprints/2002-18.pdf

Since the notion of circular language in the question is the conjunction of these two properties, it is decidable if a regular language is circular.

Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186