An algorithm for testing whether a regular language is a code

Nguyễn Đình Hân, Hồ Ngọc Vinh, Phạm Trung Huy, Đỗ Long Vân

Abstract


We present an extension of the test proposed by Sardinas and Patterson (1953) for deciding whether a set of words is a code. As a consequence, we obtain an effective algorithm that decides in ${\cal O}(k)$ time whether a given regular language is a code, where $k$ is the finite index of the syntactic congruence of this language.




DOI: https://doi.org/10.15625/1813-9663/27/1/457

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology