• 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
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3256426