科研之友
微信
新浪微博
Facebook
分享链接
摘要
We present schemes of deterministic finite automata such that, for every nontrivial automaton A resulting from the scheme with n states, the state complexity of the mirror image of the language L (A) equals 2 n. The construction leads to cases, where the increase in complexity is maximal in the transition from nondeterministic devices to deterministic ones. We also discuss the crucial importance of the size of the alphabet and present some open problems.
- 出版日期2012
