On A Measure for The Descriptional Complexity of Finite Automata with Translucent Words
摘要
We propose two parameters that should be incorporated into the measure for the descriptional complexity of deterministic and nondeterministic finite automata with translucent words: the maximal length of a translucent word and the maximal cardinality of a set of translucent words. We illustrate the influence of these two parameters on the expressive capacity of finite automata with translucent words, where we concentrate, in particular, on automata over a binary alphabet. We establish that the restrictions for the length of the longest word in any set of translucent words and the restriction for the cardinality of the admitted sets of translucent words yield a two-dimensional infinite hierarchy of classes of binary languages.