由单个状态生成的有限自动机的一些性质

1、T28 1202102$Vol. 28 No. 1Feb. 2021CHINESE JOURNAL OF ENGINEERING MATHEMATICS$:1005-3085(2021)01-0055-06Th$%$%fl1,21 , $1 , %1(1- ff$,: 541004; 2- ;fi, ; 551700) : $fR%$%,$fR%$%,fR% $ M 0 $ y% M %R% $ 1.: $: AMS(2000) 11B85$: $: A1$%yfi%,fl$fi%,yI$f%.$fi,$R%$f$% y,%f$%.%$f$%K%1-7 .K,$R%$%Q, 8 KfR% ,

2、9 fR%$%$%$%,%L%fR%$%$.$f R%$%,$fR%$% R%fi,R% $ y% .$% $%$%.f$%$ 9,10.2y$ 1 $ M =(X, Y, S, , ) R%$, s0 S,K s S, X , S = (s0 , ),% S = (s0 , ) | X .% s0 M %R.%,fi$R%$.y 1 M =(X, Y, S, , ) %$,s0 S,% M s0 R, M % s0 %. 1 M = (X, Y, S, , ) %$,B S %, M % B $%.$: 2007-08-07. $: fl (19818$R),Q,T. :%. : (6047

3、3005):ff (0832103):ffR (2007106020701M48).y$ 2 M = (X, Y, S, , ),M r = (Y, X, Sr, r, r) %$, s S,Q sr Sr,K X ,$ r(sr, (s, ) = 0 ,$ | = , sr s % . sr Sr,Q s S, sr % s % , sr % . 1 M = (X, Y, S, , ),M r = (Y, X, Sr, r, r) %$,sr Sr % s0 S %0 ,K% X ,r(sr , (s0 , ) (s0 , ) % .0 2 M = (X, Y, S, , ) s0 R, M

4、 %R%$ M % . 10,M = (X, Y, S, , ) %$ M % .f s0 S,% s0 ,% s0 % , s0 R% M %$ ,%f%. 3 M = (X, Y, S, , ) $,s0 S, s0 % s0 R% M %$ M1 .fR%$.y 2 M = (X, Y, S, , ) M r = (Y, X, Sr, r, r) %R%$,M r % M % , sr Sr % M % % Gr(z)sr = 0,$ Gr(z) M r %,M $ M %. M M r % H (z) H r(z). 3, $ H r(z)H (z) =zr I ,I . sr % M

5、 % ,K% X ,$ r(sr, (M , ) = 0 ,$ 0 X . Gr(z)sr + H r(z)H (z)X (z) = X (z) + z X (z),$ X (z), X (z) 00 , 0 %R,f M r % M % , H r(z)H (z) = z I ,f G (z)s =rrrkX0 (z).,M r M r R, sr = r(M r , ), X , k 0,r(M r , )r(sr, (M , ) = r(M r , )r(r(M r , ), (M , )= r(M r , (M , ) = r(M r , )0 ,%Gr(z)M r + H r(z)(

6、X (z) + zk H (z)X (z)= Gr(z)M r + H r(z)X (z) + zk (X (z) + z X (z),0H r(z)X (z) + zk H r(z)H (z)X (z) = H r(z)X (z) + zk X (z) + zk+ X (z),0$ X (z) % %R,f zk X (z) = 0, Gr(z)sr = X (z) = 0.00 sr Sr fl Gr(z)sr = 0,K% X ,r(sr, (M , ) %RGr(z)sr + H r(z)(G(z)M + H (z)X (z) = Gr(z)sr + H r(z)H (z)X (z)

7、= z X (z), r(sr, (M , ) = 0 ,$ 0 $fifi. sr % M % .fl,% M r % M r % M % ,% M % % M r . 2 M = (X, Y, S, , ) %R%$, M r = (Y, X, Sr, r, r)% M % % sr Sr,K% X ,r(sr, (M , ) = 0 ,$ M % M %,|0 | = . .K% s S, X , M R, X , s = (M , ), (s, ) = (M , ), ),f(M , )(s, ) = (M , )(M , ), ) = (M , ), sr Sr, r(sr, (M

8、, ) = 0 , |0 | = ,%r(sr, (M , ) = r(sr, (M , )(s, )= r(sr, (M , )r(r(sr, (M , ), (s, ) = 0 = rr ,0$ |r| = |, |r | = ,f r(sr, (M , ),0r(r(sr, (M , ), (s, ) = r , |r | = ,00 s %K M r % M % . 3 M = (X, Y, S, , ) %R%$,M r = (Y, X, Sr, r, r) %$,%flK% sr Sr, X , sr Sr,0sr = r(sr , (M , ),0 M r % M % %K% s

9、r Sr, X , 0 X ,r(sr, (M , ) = 0 .3 M1 = (X, Y, S1 , 1 , 1 ),M2 = (Y, Z, S2 , 2 , 2 ) %$,M1 M2 % (K) $ C (M1 , M2 ) = (X, Z, S1 S2 , , ),$(s1 , s2 ), x) = (1 (s1 , x), 2 (s2 , 1 (s1 , x),(s1 , s2 ), x) = 2 (s2 , 1 (s1 , x), (s1 , s2 ) S1 S2 ,x X.h M1 M2 .$ M WIFA M . WIFA M %,fl WIFAM1 M2 , M M1 M2 .

10、y$ 31$ M = (X, X, X, , ) y,$(x, xr) = xr,(x, xr) = x, x, xr X, Md . Md % M d ,Q$ y. 1,2 %,$ M = (X, Y, S, , ), M %K s $ r,fW Mr,s = (s, x0 , , xr1 ) | x0 , , xr1 X , s %$ r $.|W M | r,M = min |W M |r,sr,ssS s %$ r $ M %$ r $. M = (X, Y, S, , ) %$,s S, y Y ,$Out(s) = (s, x) | x X ,d(s) = |Out(s)|,St

11、(s, y) = t S | x X, s.t. t = (s, x) and (s, x) = y. 4 M = (X, Y, S, , ) s0 S R%fl 1 WIFA,|X | = |Y |,%K s S,d(s0 ) d(s), M %$% 1. |X | = |Y | = n, M %fl 1 %,K% s S, delay(s) 1 (delay(s) $ s % 2). d(s0 ) , d(s0 ) n. 4 % 2,K% sr S, d(sr) = d(s0 ) = n, |X | = |Y | = n,K% sr S,Q (sr, x) = (s, y),x, y X

12、, x = y,f sr 0 . M fl 1 z.f d(s) = d(s0 ) 1, M 0 WIFA y% |W M | = 1.r,s0 4 M = (X, Y, S, , ) R% $,%K s S = (M , ) | X k , k ,(s, 0) = 0, M 0 WIFA y. M = (X, Y, S, , ) %R% $,Q M 0 WIFA y, 4,$ |W M | = 1.%K 1 , 2 r,MX ,1 = 2 ,(M , 1 ) = (M , 2 ), (M , 1 0 ) = (M , 2 0 ). 1 0 , 2 0%R X1 (z), X2 (z),M %

13、 H (z), H (z)X1 (z) = H (z)X2 (z),% H (z)X1 (z) X2 (z) = 0, 11 % 1 X1 (z) X2 (z) = 0,% X1 (z) = X2 (z), 1 0 = 2 0 ,% 1 = 2 . 1 = 2 z. 5 M = (X, Y, S, , ) s0 S R%fl 1 WIFA,|X | = |Y | = n % 1,M = 1. 1 M = (X, Y, S, , ),$ X = Y = a, b, c, d, e, f ,S = s1 , s2 , $f:1,|W M | = 1,M , M 0 WIFA 1 y% n 1,s0

14、(s1 , a) = s1 ,(s1 , b) = s2 , (s1 , c) = s1 , (s1 , d) = s2 , (s1 , e) = s1 , (s1 , f ) = s2 ,(s1 , a) = a;(s1 , b) = a; (s1 , c) = b; (s1 , d) = b; (s1 , e) = c; (s1 , f ) = c;(s2 , a) = s1 ,(s2 , b) = s2 , (s2 , c) = s1 , (s2 , d) = s2 , (s2 , e) = s1 , (s2 , f ) = s2 ,(s2 , a) = d;(s2 , b) = d;

15、(s2 , c) = e; (s2 , d) = e; (s2 , e) = f ; (s2 , f ) = f.%, M R%$,s1 , s2 % M %R.% M $y.f 1 %$%fl:fl % % n y WIFA M %$y?$:1 $. $%KJ. $:A ,1993, 23(7): 759-765Bao F. Composition and decomposition of weakly invertible finite automataJ. Science in China, Series A,1993, 23(7): 759-7652 I. $%flJ. Q,2005,

16、 42(4): 690-696Wang H J. Two results of decomposing weakly invertible finite automataJ. Journal of Computer Research and Development, 2005, 42(4): 690-6963 ,$,%. $%J. ,2005, 28(9): 1501-1507Cao F, Deng P M, Yi Z. Decomposition of weakly invertible finite automataJ. Chinese Journal of Com- puters, 20

17、05, 28(9): 1501-15074 y,$fl,$. $%J. ff$:,2006, 24(1):30-33Yan H Y, Xie Z W, Deng P M, et al. Functions of zero state of linear finite automataJ. Journal of GuangxiNormal University (Natural Science Edition), 2006, 24(1): 30-335 ,$. y$%J. ,1994, 17(5): 330-337Gao X, Bao F. Decomposition of binary wea

18、kly invertible finite automataJ. Chinese Journal of Computers,1994, 17(5): 330-3376 . $%flJ. ,1993, 16(8): 629-632Gao X. Two results about the decomposition of delay step of weakly invertible finite automataJ. ChineseJournal of Computers, 1993, 16(8): 629-6327 ,$,%. Moore %J. ff$:,2003, 21(4):44-47C

19、ao F, Deng P M, Yi Z. Some results of invertibility of moore automataJ. Journal of Guangxi NormalUniversity (Natural Science Edition), 2003, 21(4): 44-47 8 %. %J. ,1987, 30(5): 679-687Shen H. Semigroup structure of automataJ. Acta Mathematica Sinica, 1987, 30(5): 679-687 9 . $%M. fl:$,1979Tao R J. I

20、nvertibility of Finite AutomataM. Beijing: Science Press, 1979 10 . M. fl:$,1986Tao R J. Introduction to Finite AutomataM. Beijing: Science Press, 198611 ,. $%-%J. $ (A),1996, 26(5): 429-436Dai Z D, Ye D F. Invertibility of linear finite automata-classification and enumeration of transfer functionJ.

21、 Science in China, Series A, 1996, 26(5): 429-436Some Characteristics of Finite Automata Generated by Single StateHUANG Fei-dan1,2 , MENG Chun-feng1 , DENG Pei-min1 , YI Zhong1(1- College of Mathematical Science, Guangxi Normal University, Guilin 541004;2- Department of Mathematics, Bijie College, Bijie, Guizhou 551700)Abstract: This paper investigates the weakly invertible and decomposable properties of the finiteautomata generated by a singl