Algebraic Theory of Automata and Languag by Masami Ito PDF

By Masami Ito

ISBN-10: 9810247273

ISBN-13: 9789810247270

Even if there are a few books facing algebraic idea of automata, their contents consist usually of Krohn–Rhodes thought and similar themes. the subjects within the current e-book are relatively assorted. for instance, automorphism teams of automata and the in part ordered units of automata are systematically mentioned. furthermore, a few operations on languages and exact periods of standard languages linked to deterministic and nondeterministic directable automata are handled. The publication is self-contained and for that reason doesn't require any wisdom of automata and formal languages.

Show description

Read or Download Algebraic Theory of Automata and Languag PDF

Similar algebra books

Download e-book for iPad: Structure and representations of Jordan algebras by N. Jacobson

###############################################################################################################################################################################################################################################################

Extra info for Algebraic Theory of Automata and Languag

Sample text

1 Let A = (G^,, X , 6,) be a regular (n,G)-automaton and E be a homomorphism of G onto some group. Then J(G) is isomorphic to a subgroup of G ( A /Ker(<)). 40 CHAPTER 1. 1. By the so-called homomorphism theorem, we have the following Fleck's result [18]. 2 Let A = ( S ,X , 6) be a strongly connected automaton and H be a normal subgroup of G ( A ) . T h e n G ( A ) / H is isomorphic to a subgroup of G ( A / H ) . 3 Let A = X , 6,) be a regular (1,G)-automaton and J be a homomorphism of G onto some group.

Then we have lSllXl 2 I(G)IGI where I ( G ) = min{(H( 1 H G, [HI = G } and [HI is the subgroup of G generated b y the elements of H . e. A is a regular (n,G)-automaton. Then it is enough to show that n IGI 1x1 2 I ( G ) IGI. Let 'k(a)fl be the set of all nonzero components of Q ( a ) where a E X. Then obviously l'@(a)gl 5 n holds. By the strong connectedness of A , we obtain immediately = G. Thus we have CHAPTER 1. GROUP-MATRIX T Y P E AUTOMATA 32 2 I ( G ) . On the other hand, n l X l 2 Hence we have n (GI (XI1 I ( G ) (GI.

N ) be the element of the symmetric group S ( n ) on { 1,2,3,. . , n}. Moreover, we assign Q ( z ) = e F ( q l ) E where e is the identity of G. Thus we can define an (n,G)-automaton A= X,Sq). ( (c, Now, we prove that A is regular. Proof of the strong connectedness of A First, we prove that, for any i , j = 1 , 2 , ,. ,n and all h E H , there exists an element z E X* such that the (i,j)-entry of Q(z) is equal to h. By the assignment of Q ( Y ) ,for any h E H there exist some integers s = 1 , 2 , .

Download PDF sample

Algebraic Theory of Automata and Languag by Masami Ito


by Mark
4.4

Rated 4.95 of 5 – based on 9 votes