Unique decipherability of infinite regular language 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.
McCloskey gave such an algorithm in his paper An $O(n^2)$ Time Algorithm for Deciding
Whether a Regular Language is a Code. Given an NFA on $n$ states, his algorithm runs in time $O(n^2)$. Since a regular expression of length $n$ can be converted to an NFA with $O(n)$ states in linear time, McCloskey's algorithms runs in quadratic time even when given a regular expression as an input.