# 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.

## 1 Answer

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.