Size of nondeterministic and deterministic automata for certain languages

被引：0

作者：

Ozols, R ^{[1
]}

Freivalds, R ^{[1
]}

Mancinska, L ^{[1
]}

Ozols, M ^{[1
]}

机构：

[1] Latvian State Univ, Dept Comp Sci, LV-1459 Riga, Latvia

来源：

FCS '05: PROCEEDINGS OF THE 2005 INTERNATIONAL CONFERENCE ON FOUNDATIONS OF COMPUTER SCIENCE | 2005年

关键词：

deterministic automata; nondeterministic automata; states;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the theory of automata the question about difference between the size of deterministic and nondeterministic automata, which recognize the same language, is of great importance. However, this problem has been studied mainly in case when input alphabet consists of at least 2 letters. In this paper some special kind of languages in one letter alphabet will be discussed and the estimate of the number of states required for deterministic and nondeterministic automata to accept these languages will be made. For one of these languages nondeterministic automaton with <= [ root n] + 1 states can be built, but for other with <= 1.8. (/ In 2 n)(In In n) + 0,85. ((In In n)2) (/In 2 n) states, where n is the number of states required for the corresponding deterministic automaton.

引用

页码：169 / 175

页数：7