Độ phức tạp otomat hữu hạn đoán nhận siêu ngôn ngữ chính quy

Đặng Huy Ruận, Phùng Văn Ổn

Abstract



We shall call the  small possible number of states of a hyper-finite deterministic automaton, which recorgnizes the set of word L in the alphabet ∑, a complexity of a finite automaton of L, and denote by P(L). We have the following result:

For any hyper-generating schemar G, the complexity of a finite automaton of L(G) is:

P(L(G)) ≤ 2 D + 1.




DOI: https://doi.org/10.15625/1813-9663/14/4/7964

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology