DocumentCode :
3256426
Title :
Obtaining tight upper-bounds for the state complexities of DFA operations
Author :
Yu, Sheng ; Zhuang, Qingyu ; Salomaa, Kai
Author_Institution :
Dept. of Comput. Sci., Univ. of Western Ontario, London, Ont., Canada
fYear :
1992
fDate :
28-30 May 1992
Firstpage :
100
Lastpage :
104
Abstract :
The authors consider the state complexity of basic operations of regular languages. They show that the number of states that is sufficient and necessary in the worst case for a deterministic finite automaton (DFA) to accept the catenation of an m-state DFA language and an n-state DFA language is exactly m2n-2n-1, for m, n>1. The result of 2n-1+2n-2 states is obtained for the star of an n-state DFA language, n>1. State complexities for other basic operations and for regular languages over a one-letter alphabet are also studied
Keywords :
computational complexity; deterministic automata; finite automata; formal languages; DFA language; catenation; deterministic finite automaton; n-state DFA language; one-letter alphabet; regular languages; Automata; Computer science; Councils; Doped fiber amplifiers; Mathematics; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computing and Information, 1992. Proceedings. ICCI '92., Fourth International Conference on
Conference_Location :
Toronto, Ont.
Print_ISBN :
0-8186-2812-X
Type :
conf
DOI :
10.1109/ICCI.1992.227695
Filename :
227695
Link To Document :
بازگشت