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.


Full Text: PDF

Refbacks

  • There are currently no refbacks.


Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology