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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On A Measure for The Descriptional Complexity of Finite Automata with Translucent Words

  • František Mráz,
  • Friedrich Otto

摘要

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.