Can we design an algorithm to test if a infinite regular language is a code?
We have the S-P algorithm to determinate if a finite language is a code. But how about the infinite part of regular languages?
If we have a regex which describes our set of words, then is it possible to modify the S-P algorithm to work on an infinite set without creating Pattern Matching Machines? If it helps, let the regex use only ‘* | ()’ as special symbols.
I thought about making an algorithm which would work based on a PMM, but it isn’t as trivial as the S-P algorithm for finite sets, checking the suffixes of strings with matching prefix. The algorithm would be creating a PMM from the regex and traversing it for the search of suffixes etc. like in the S-P algorithm.