Thumbnail
Access Restriction
Subscribed

Author Sheng Yu ♦ Qingyu Zhuang ♦ Salomaa, K.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©1992
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Doped fiber amplifiers ♦ Automata ♦ Upper bound ♦ Computer science ♦ Mathematics ♦ Councils
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 m2/sup n/-2/sup n-1/, for m, n>1. The result of 2/sup n-1/+2/sup n-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.<<ETX>>
Description Author affiliation: Dept. of Comput. Sci., Univ. of Western Ontario, London, Ont., Canada (Sheng Yu; Qingyu Zhuang)
ISBN 081862812X
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1992-05-28
Publisher Place Canada
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 270.20 kB
Page Count 5
Starting Page 100
Ending Page 104


Source: IEEE Xplore Digital Library