2
$\begingroup$

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.

$\endgroup$
1
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.