Độ 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
Author affiliations

Authors

  • Đặng Huy Ruận Publishing House for Science and Technology
  • Phùng Văn Ổn

DOI:

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

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.

Metrics

Metrics Loading ...

Published

29-03-2016

How to Cite

[1]
Đặng H. Ruận and P. V. Ổn, “Độ phức tạp otomat hữu hạn đoán nhận siêu ngôn ngữ chính quy”, JCC, vol. 14, no. 4, p. 25–30, Mar. 2016.

Issue

Section

Computer Science