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


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: Display counter: Abstract : 219 views. PDF (Tiếng Việt) : 109 views. PDF : 35 views.


Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology