Group과  Semigroup의 정의는 무엇인가 생각하여 보시오.  또,  이러한 추상적인 model의 가장 기본적인 예는 무엇인가 생각하여 보시오.

 Discrete한 구조를 이해하기 위하여 필요한 여러

수학 이론 중에서 먼저 기본적인 semigroup 과

group의 개념을 알아보고 computer 이론에

활용하는 방법에 관하여 학습하도록 한다.

   Semigroups and Groups

Discrete한 구조를 이해하기 위하여 필요한 여러

수학 이론 중에서 먼저 기본적인 semigroup 과

group의 개념을 알아보고 computer 이론에

활용하는 방법에 관하여 학습하도록 합시다.

다음의 강의 내용은 B. Kolman, R.C. Bussy & S.

Ross의 저서인

Discrete Mathematical Structures,

Prentice Hall Inc., 1996.

의 9장의 내용을 참고하여 학습하기 바랍니다.

(1) Binary Operations Revisited

◆ A binary operation on a set A is an

everywhere defined function f : A x A→A

- f  is defined for each ordered pain of (a,b)

-  only one element of A is assigned to each     (a,b)

-  if a,b∈A then a*b∈A ; A is closed under     the operation *

◆ Properties of binary operations.

- a binary operation * on a set A is said to be    commutative  if a*b = b * a for all a,b∈A

- a binary operation * on a set  A is said to be    associative  if

    a*(b*c)= (a*b)*c    for all a,b,c∈A

- a binary operation * on a set is said to be    idempotent  if a*a = a for all a∈A

(2) Semigroups

◆  A Semigroups is a nonempty set S together     with an associative binary operation *     defined on S.

- we refer to a*b  as the product of a and b.

- the semigroup (S,*) is said to be    commutative if * is a commutative operation.

- let A = (a₁, a₂, ... , a_n) be a nonempty set,   then (A^*,^, (concatenation)) is a semigroup   since (α^,β)^,γ = α^,(β^,γ) for α,β,γ∈A^* .

  The semigroup (A^*, ^, ) is called the  free   semigroup generated by A

◆ An element e in a semigroup  (S,*) is called

   an identity if e*a=a*e=a  for all a∈S

   (Example) The number 0 is an identity in the   semigroup (Z,+)

   The semigroup (Z⁺,+)  has no identity    element.

- If a semigroup (S,*)  has an identity, it is unique.

[Suppose that e and e' are identity elements in S, then e*e'=e' and e*e'=e', hence e = e'.]

◆A monoid is a semigroup (S,*) that has an   identity.

◆ Let (S,*) be a semigroup and T⊂S

- If T is closed under the operation *, then

  (T,*) is a subsemigroup of (S,*).

- If e (identity)∈T,  then (T,*) is a submonoid

   of (S,*).

◆ Let (S,*) and (T,*') be two semigroups.

- a function f:S→T  is called an isomorphism

from (S,*) to (T,*')  if it is one to one

correspondence and f(a*b)=f(a)*'f(b)  for

every a, b in S.

-f is an isomorphism from S to T, then

f^-1 is an isomorphism from T to S.

 

Example.  Let T be the set of all even integers, then ( Z ,+) and ( Z ,+) are isomorphic define f : Z →T by f(a) = 2a, thenf is one-to-one and  onto (hence one-to-one correspondence) and f(a+b) = 2(a+b) = 2a + 2b = f(a) + f(b) .

 

Theorem 2. Let (S,*) and ( T,*') be monoids with respective identities e and e'. Let f : S→T be an isomorphism, then f(e)=e'.

Proof. Let a∈ S and b∈ T and f(a) = b

b = f(a) = f(e*a) = f(a)*'f(e)=b*'f(e), hence

f(e)=e'.   Q.E.D.

◆ Let (S,*) and ( T,*') be two semigroups.

- an everywhere defined function f : S→T is

called a homomorphism from (S,*) to ( T,*') if

f(a*b) = f(a)*'f(b) for every  a, b in S.

- if f is also onto T is the homomorphic image

of S.

 

Theorem 4. Let f be a homomorphism from a semigroup (S,*) to semigroup ( T,*')    If S' is a subsemigroup of (S,*) then f(S'), the image of S' under f is a subsemigroup of ( T,*').

Proof.  If  t₁,t₂∈ f(S') then t₁=f(s₁) and

t₂=f(s₂) for  some s_1,s_{2 .}

t₁*' t₂ = f (s₁ ) *'f (s₂ ) = f (s₁*s₂ ) = f (s₃)

where s3∈ S',  hence t₁*' t₂ = f(S')

 Q.E.D.

 

Theorem 5. If f is a homomorphism from a commutative semigroup (S,*) onto a semigroup ( T,*')   then ( T,*')   is also commutative .

Proof. Let t₁,t₂∈ T then t₁= f(s₁) and

t₂=f(s₂) for s_1,s₂∈S.

    t₁*' t₂ = f (s₁ ) *'f (s₂ )

  =  f (s₁*s₂ ) = f (s₂*s₁ ) = f (s₂ ) *'f (s₁)

  = t₂ *' t_1.   

  Q.E.D.

 (3) Products and Quotients of      Semigroups

 

Theorem 1.  If (S,*) and ( T,*')  are semigroups then ( S x T,*'') is a semigroup, where *'' is defined by s1,t1*'' s2,t2=(s1*s1 , t1*' t2 ).

 ◆ An equivalence relation R on the semigroup

(S,*) is called a congruence relation if  aRa'

and bRb'  implies (a*b)R(a'*b' ).

 

Example.   Let A ={0,1} . Consider the semigroup (A*, . ) : αRβ  iff α and β have the same number of 1's (α,β∈A*) αRα  for any α∈A*, if αRβ then βRα αRβ and βRγ, then αRγ. Hence R is an equivalence relation αRα' and βRβ'  then (α,β)R(α',β' ) Hence R is a congruence relation.

◆Let [a] be the equivalence class containing

a, and let S/R be the set of all equivalence

classes.

 

Theorem 2. Let R be a congruence relation on the semigrouop (S,*) . Consider the relation   from S/R x S/R to S/R where ([a],[b]) is related to [a*b].  Then we have    (a) is a function from       .    (b) (S/R,) is a semigroup.

Proof. (a) Suppose ([a],[b]) = ([a'],[b']) ,

then and  aRa' and bRb'  so a*bRa'*b' , thus

([a],[b]) = ([a'],[b']) ; that is,   is a

function .

(b)  [a] ([b] [c]) = [a]  [b*c ]

   = [a*(b*c) ] = [(a*b)*c ]

   = [a*b] [c] = ([a] [b]) [c]

◆ S/R is called the quotient semigroup or

factor semigroup.

 Example.  S=(A^{*, .} ) , A = {0, 1},

then (S/R,⊙ ) is a monoid where

[α]⊙[β]=[α^.β].

 

Theorem 3. Let R be a congruence relation on a semigroup (S,*), and (S/R, )  let be the corresponding quotient semigroup, Then the function fR:S→S/R defined by fR(a)= [a] is an onto homomorphism .

Proof. If [a]∈S/R then f_R(a)= [a] so f_R is

onto. Let a,b∈S, then

  f_R(a*b)= [a*b]=[a] [b]=f_R(a)f_R(b)

◆  f_R : S → S/R  is called

    the natural homomorphism.

 

Theorem 4. Let f : S→T be a homomophism of the semigroup (S,*) onto the semigroup . Let R be a relation on S defined by aRb iff f(a) = f(b) a,b∈S. Then (a) R is a congruence relation; (b) (T,*')  and the quotient semigroup     (S/R, ) are isomorphic .

Proof. (a) It is easy to show that R is an

equivalence relation. Suppose aRa' and bRb'.

Then f(a) = f(a') and f(b) = f(b')

f(a) *'f(b) = f(a') *'f(b')

f(a*b) = f(a'*b') , hence a*bRa' *b'

(b) Define : S/R →T as follows

([a]) = f([a])  for each  [a] in S/R.

Suppose [a]=[a'] then aRa' so f(a) = f(a') ,

hence is a function.

Suppose that ([a]) = ([a']) then f(a) =

f(a'),  so aRa' ⇒ [a]=[a'], hence is

one-to-one.

Suppose b∈T, then f(a) = b   a∈T.

then ([a]) = f(a) = b , hence  is onto.

Finally,

  ([a][b])=([a*b]) = f(a*b) =f(a) *'f(b)

                  = ([a]) *' ([a])

( °f_R)(a) = (f_R(a)) = [(a)]= f(a)

(4)  Groups

◆A group is a set G together with a binary

operation * on such that

1.(a*b)*c  a* (b*c)  for a,b,c ∈G;

2. there is unique element e in G such that

a*e = e*a  = a  for a ∈G;

3. For every a ∈G  there is a' ∈G

(inverse of a) such that a*a' = a'*a  = e.

◆A group G is said to be abelian if a*b =

b*a for all a,b ∈G.

 

Theorem 1. Let G be a group. Each element a ∈G has only one inverse in G.

Proof. Let a and a' be inverse of a.

Then a'(aa'') = a'e=a'

a'(aa'') =ea'=a''  Hence a'=a''.

Q.E.D.

◆ We denote the inverse of a by a^-1.

 

Theorem 2. Let G be a group and a,b,c∈G . Then    (a) ab = ac ⇒ b = c;    (b) ba = ca ⇒ b = c.

 

Theorem 3. Let G be a group and a,b∈G.   Then    (a) (a-1)-1 = a ;    (b) (ab)-1= b -1 a -1.

 

Theorem 4. Let G be a group and  a,b∈G . Then    (a) The equation ax = b has a unique         solution in G.    (b) The equation ya = b has a unique         solution in G.

Proof. (a) x = a ^-1b is a solution since a(a ^-1b)= (aa^-1)b = eb = b.

Suppose x₁ and x₂  are two solution of ax = b.

Then ax₁ = b  and ax₂ = b Hence ax₁ = ax₂ ⇒ x₁ = x₂ .

 

문제 1.    위 정리 4의 (b)를 증명하시오.

◆ If a group G  is finite, binary operation * can

be given by a table.

- from Theorem 4, each element b  must

appear exactly once in each row and column of

the table.

◆ If G   is a group that has a finite number of

elements, we say that G  is a finite group and

order of G is |G|.

The following is the multiplication table for

groups of orders 1, 2, 3 .

- The groups of orders 1, 2 and 3 are also

abelian and that there is just one group

of each order for a fixed labeling of the

elements .

◆ Let H be a subset of a group G  such that

(a) e∈H

(b) if a,b∈H then ab∈H

(c) if a∈H then a^-1∈H

then H is called a subgroup of G.

 

Theorem 5. Let (G,*) and (G',*')  be two groups, and let f:G→G' be a homomorphism from G to G'.  The we have   (a) If e∈G  and e'∈G'  are identities then    f(e)=e'. (b) If a∈G, then f(a-1)=(f(a))-1. (c) If H is a subgroup of  G,  then  f(H) ={f(h) | h∈H} is a subgroup of G'.

Proof. Let x=f(e). Then

x*x'=f(e)*'f(e)=f(e*e)=f(e)=x so x*'x=x

multiply both sides by x^-1

x*'x*'x^-1 = x*'x^-1⇒x*e'=e'⇒x=e' so  f(e)=e'

f(a^-1*a) =f(a^-1) *'f(a) =f(e)=e'

Hence f(a^-1) =(f(a)) ^-1.

Q.E.D.

 

문제 2.   위 정리 5의  (b), (c)를 증명하시오.

(5) Products and Quotients of     Groups

 

Theorem 1. If G1 and G2 are groups, then G=G1xG2  is a group with operation defined by (a1,b1)(a2,b2) = (a1a2 , b2b1).

 

Theorem 2. Let R be a congruence relation on the group (G,*). Then the semigroup (G/R,) is a group, where the operation is defined on G/R  by [a] [a]=[a*b].

Proof. Since a group is a monoid G/R   is a

monoid. Let [a]∈G/R, then [a^-1]∈G/R and

    [a][a^-1]=[a*a^-1]=[e].

So [a]^-1=[a^-1] hence (G/R,)  is a group.

 Q.E.D.

 

Corollary 1. (a) If R is a congruence relation on a group , then the function fR:G→G/R given by fR(a)= [a] is a group homomorphism. (b) If f:G→G' is a homomophism from the group (G,*) onto the group (G',*'), and R is a relation defined on G by aRb iff f(a)=f(b) , a,b∈G; then we have (1) R is a congruence relation; (2) The function :G/R→G' , given by ([a])=f(a) is an isomorphism from the group (G/R,) onto the group (G',*').

  Discrete한 구조를 이해하기 위하여 필요한 여러

수학 이론 중에서 먼저 기본적인 semigroup 과

group의 개념을 알아보고 computer 이론에

활용하는 방법에 관하여 학습하도록 한다. 

 언어와 문법의 관계는 무엇인가 ?  또 효율적인 문법이 갖추어야할 성질은 무엇인가 생각하여 보시오.

 Discrete한 구조를 이해하기 위하여 필요한 여러

수학 이론 중에서 formal language에 관한 학습으로

먼저 새로운 수학적 구조인 phrase structure

grammer와 유용한 formal language를 만들기 위한

단순한 방법에 관하여 학습하도록 한다.

    Languages and Finite State Machines

Discrete한 구조를 이해하기 위하여 필요한 여러

수학 이론 중에서 formal language에 관한 학습으로

먼저 새로운 수학적 구조인 phrase structure

grammer와 유용한 formal language를 만들기 위한

단순한 방법에 관하여 학습하도록 한다.

다음의 강의 내용은 B. Kolman, R.C. Bussy & S.

Ross의 저서인

Discrete Mathematical Structures,

Prentice Hall Inc., 1996.

의 10장의 내용을 참고하여 학습하기 바랍니다.

(1) Languages

Refer the pp. 368-377 of the book :

B. Kolman, R.C. Bussy & S. Ross,

Discrete Mathematical Structures,

Prentice Hall Inc., 1996.

(2) Representation of Languages     and Grammers

Refer the pp. 378-390 of the book :

B. Kolman, R.C. Bussy & S. Ross,

Discrete Mathematical Structures,

Prentice Hall Inc., 1996.

(3) Finite state machine

◆ Finite state machine

-S : state set

-I : input set

-F : set of state transition function f_x: S→S for each x∈I

◆ We may define F :S x I →S  given by

    F(S_i,x)=F_x(S_i).

◆ We can define a relation R_M on S such that

S_iR_MS_{j  if there is an input x so that}  f_x(S_i)=S_j

◆Moore machine or recognition machine

M=(S,I,F,s₀,T) where S0∈S is the starting state

and T⊆S is the set of acceptance states.

◆ Let M=(S,I,F) be a finite state machine, and R

is an equivalence relation on S.

R  is a machine congruence on M  if for any

s,t ∈ S, sRt  implies that f_x(s) R f_x(t) for all x∈I.

◆ Let R be a machine congruence on M=(S,I,F)  

and let =S/R be the partition of S corresponding

to R. Define _x([S])=f ([S]), then = (,I,) is

a finite state machine called the quotient of

corresponding to R .

◆ If M=(S,I,F,s₀,T)  is a Moore machine and R is

a machine congruence on M then we may let

   = {[t] | t∈T}.

=(,I,,) is called the quotient Moore machine

of M.

(4) Semigroups, Machines and     Languages

◆  Let M=(S,I,F)  S= {s₀,s₁,...,s_n} ,

    F={f_x|x∈ I}.

- I^* is a monoid with catenation as its binary

operation and identity e = ∧(empty string).

- let S³  be the set of all functions from S to S³,

  then is a monoid with composition as its binary

  operation, and identity of is the function I₃

  defined by I3(s )= s  for all s∈ S.

- if w=x₁ , x₂ ,x₃ , ... , x_n ∈ I^* .

  We let  f_w (state transition function corresponding to w) .

  

Theorem 1. Define a function T:I*→S3  as T(w), then   (a) if w1 , w2 ∈ I*  then      T(w1 .w2 )=   T(w2)=T(w1).   (b) if M=T(I*) then M is a submonoid of S3.        T is a homomorphism from I* to S3.

◆ For a Moore machine M=(S,I,F,s₀,T),

- define L(M)  to be the set of all w ∈ I^* such

  that f_w(s₀) ∈ T.

- L(M) is called the language of the machine M.

(5) Machine and Regular languages

 

Theorem 1. Let I be a set and L⊆I*. L is a type 3 language iff L=L(M) for some Moore machine M.

 

Corollary 1. L=L(M) for some Moore machine M iff L is a regular set.

◆ Construction of the type 3 grammar for a given

Moore machine M=(S,I,F,S0,T),  G=(V,I,s₀,)

where V = I∨S;

   write s_i xs_j   if f_x(s_i)=s_j ,  and

   write s_i x    if f_x(s_i)∈T.

 

Example 2. Consider the machine of Example 1. Here S ={s0,s1,s2,s3} and T={s2,s3}. We use the method above to compute an equivalent quotient machine. First ,P0={{s0,s1},{s2,s3}}. We must decompose this partition in order to find P1. Consider first the set {s0,s1}.Input 0 takes each of these states into {s0,s1}. Input 1 takes both s0 and s1 into {s2,s3}. Thus the equivalence class {s0,s1}dose not decompose in passing to P1. We also see that input 0 takes both s2 and s3 into {s2,s3} . and input 1 takes both s2 and s3 into {s2,s3} . Again, the equivalence class {s2,s3} dose not decompose in passing to P1. This means that P1=P0, so P0 corresponds to the congruence R. We found this result directly in Example1.

 

Example 3. Let M be the Moore machine shown in Figure 10.54. Find the relation R and drow the digraph of corresponding quotient machine .

Solution : The partition P₀ = {T,} = {{s₀,s₅} ,{s₁,s₂,s₃,s₄} }.Consider first the set {s₀,s₅}. Input 0 carries both s₀ and s₅ into T, and input 1 carries both into . Thus {s₀,s₅} does not decompose further in passing to P₁. Next consider the set ={ s₁,s₂,s₃,s₄} . State s₁ is carried to by input 0 and to T by class of s_↓ in P_↓ will be {s₁,s₄} . Since states s₂ and s₃ are carried into by input 0 and 1, they will also form an equivalence class in P₁,Thsu has decomposed into the subsets {s₁,s₄} and {s₂,s₃} in passing to P₁ and P₁={ {s₀,s₅} ,{s₁,s₄} ,{s₂,s₃}}.

(6) Simplification of Machines

Let M be a Moore machine.

- for any s,t∈ S and w∈ I^* we say that  s and  t

are w-compatible if f_w(s) and f_w(t) both belong to

T or neither does.

- define a relation R  on S such that sRt iff  s and

t are w-compatible for all w∈ I^* .

 

Theorem 1.   (a) R is an equivalence relation on S;   (b) R is a machine congruence.

 

Theorem 2. Let M be a Moore machine and let R be a machine congruence. If is the corresponding quotient machine.   Then L()=L(M).

◆ Define R_k such that  sR_kt  iff s and t are

w-compatible for all w∈ I^*  with l(w) ≤k.

 

Theorem 4. (a) S/R0x={T,T'} (b) let k be a nonnegative integer and s,t ∈ S, then        s Rk+! t  iff  (1) s Rk t ;                       (2) fx(s) Rk fx(s) for all x∈ I.

 

Theorem 5. If Rk=Rk+1 then  Rk=R.

* Simplification Procedure :

(ⅰ) Start with partition P₀={T,T'}  of S.

(ⅱ) Construct P₁ ^,P₂ ^...corresponding to R₁ ^,R₂ ^..

(ⅲ) Whenever P_k= P_{k+1 ,} then stop.

(ⅳ) The resulting quotient machine is equivalent

to the given Moore machine and has the minimum

number of states.

 Discrete한 구조를 이해하기 위하여 필요한 여러

수학 이론 중에서 formal language에 관한 학습으로

먼저 새로운 수학적 구조인 phrase structure

grammer와 유용한 formal language를 만들기 위한

단순한 방법에 관하여 학습하도록 한다.