MINIMAL NFA AND BIRFSA LANGUAGES

In this pap er, we define the n otion of b iR FS A which is aresid u al fi n at e st at e au t om at on ( R FS A ) wh ose t h e reve rse is also anR F S A . Th e lan gu ages r ecogn ized by su ch au t om at a are c alled b iR FS Alanguages. We prove that the canonical R FS A of a biRFSA languageis a m in im al N FA for t h is lan gu age an d t h at e ach m in im al N FA forthis language is a sub-au tomaton of the canonical R FS A. Th is lead s toa characterization of the family of biRFSA languages. In the secon dpart of this pap er, we define the family of biseparable automata. Weprove that every biseparable N FA is uniquely min imal amon g all NFAsrecogn izin g a same language, improving the result of H . Tamm andE. Ukkonen for bidetermin istic automata