Residual Finite State Automata

• Autorzy: Denis F. , Lemay A. , Terlutte A.
• Języki publikacji: EN

Abstrakty

EN

We define a new variety of Nondeterministic Finite Automata (NFA): a Residual Finite State Automaton (RFSA) is an NFA all the states of which define residual languages of the language L that it recognizes ; a residual language according to a word u is the set of words v such that uv is in L. We prove that every regular language is recognized by a unique (canonical) RFSA which has a minimal number of states and a maximal number of transitions. Canonical RFSAs are based on the notion of prime residual languages, i.e. that are not the union of other residual languages. We provide an algorithmic construction of the canonical RFSA similar to the subset construction used to build the minimal DFA from a given NFA. We study the size of canonical RFSAs and the complexity of our constructions.

Słowa kluczowe

EN

Nondeterministic Finite Automata (NFA); saturation operator; reduction operator [fi]; canonical RFSA

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 51, nr 4
• Strony: 339--368
• Opis fizyczny: bibliogr. 14 poz.

Twórcy

autor

Denis F.

autor

Lemay A.

autor

Terlutte A.

• CMI, Technopole de Chateau Gombert, 39 rue F.Joliot Curie, 13455 Marseille Cedex 13, France,