• Author / Uploaded
• 123joaozxc

Citation preview

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

CAPITULO Nº 9 GRUPOS – SEMIGRUPOS Y MAQUINAS DE ESTADO FINITO OBJETIVOS A. GENERALES  Dar razones teóricas y fundamentales de grupos y máquinas de estado finito  Presentar la información abstracta pertinente a la teoría de grupos y máquinas de estado finito

B. ESPECIFICOS  Resolver problemas sobre grupos y máquinas de estado finito  Presentar el dominio grupos y máquinas de estado finito y sus fundamentos.  Estudiar el nivel lógicos de las estructuras algebraicas y máquinas de estado finito ESTRUCTURAS ALGEBRAICAS Todo conjunto en el que se definen una o más leyes de composición interna, una o mas leyes de composición externa, se dice que es una ESTRUCUTURA ALGEBRAICA. Se entiende por Álgebra a cierta estructura algebraica dotada de dos o más leyes de composición interna, Ejemplo álgebra lineal, álgebra Multilineal, etc. También se denomina Álgebra a la parte de las matemáticas que se dedica al estudio de las estructuras algebraicas. Por su mayor interés en nuestra área, estudiaremos con detalle a los tipos de estructuras algebraicas de simple composición, es decir, con una sola ley de composición interna y con dos leyes de composición interna). Las estructuras de simple composición son: Semigrupo, Grupo, Subgrupo.

Lic. GUILLERMO MAS AZAHAUNCHE

408

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

SEMIGRUPOS Un semigrupo es un conjunto no vacío S junto a una operación binaria asociativa * definida en S y la denotaremos al semigrupo por (S,*) o cuando sea claro que la operación * existe, como S: x * (y * z) = ( x * y ) * z (operación binaria asociativa). También se llamarán a a*b producto de a y b. S e dice que el semigrupo

(S,*) es conmutativo si * es una operación

conmutativa. x * y = y * x . Propiedad Modular( e ) A un elemento e que pertenece al semigrupo (S,*) se le llama elemento identidad (neutro), si solo si e * a = a * e = a , ∀ a∈ S . Ejemplo # 1: El conjunto P(S), donde S es un conjunto, junto con la operación de unión es un semigrupo conmutativo. Ejemplo # 2: El conjunto ℤ con la operación binaria de sustracción no es un semigrupo, ya que la sustracción no es asociativa. TEOREMA 1: Si a1,a2,a3,.......,an, son elementos arbitrarios de un semigrupo, entonces todos los productos de los elementos a1,a2,a3,.......,an que puedan formarse, insertando arbitrariamente paréntesis serán iguales. Si a1,a2,a3,.......,an son elementos de un semigrupo (S,*) se escribirán sus productos como a1*a2*a3*..................*an Ejemplo # 3: El teorema 1 demuestra que los productos ((a1*a2)*a3)*a4),

a1*(a2*(a3*a4)),

(a1*(a2*a3))*a4 son todos iguales. TEOREMA 2:Si un (S,*) tiene un elemento identidad, éste es único. Demostración: Supóngase que e y e’ son elementos identidad en S. Entonces ,ya que e es una identidad.

Lic. GUILLERMO MAS AZAHAUNCHE

409

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

e*e’=e’ Además ya que e es una identidad e*e’=e De aquí que e=e’ Un monoide es un semigrupo (S,*) que tiene una identidad. ISOMORFISMO: Si (S,*) y (T,*´) dos semigrupos: A la función f : S → T se le llama ISOMORFISMO de (S,*) en (T,*´) si es: a) INYECTIVA b) SURYECTIVA c) Se cumple: f ( a * b ) = f ( a ) *′ f ( b ) ∀ a, b ∈ S PRODUCTOS Y COCIENTES DE LOS SEMIGRUPOS Donde se obtendrán nuevos semigrupos de los ya existentes. TEOREMA 1: Si (S,*) y (T,*) son semigrupos,(S x T,*’’) es un semigrupo donde *’’ está definido por (s1, t1) *’’(s2,t2)=(s1*s2,t1*’t2)

Ahora se discutirá las relaciones de equivalencia en un semigrupo (S,*) .Como un semigrupo no sólo es un conjunto, se encontrará que ciertas relaciones de equivalencia en un semigrupo dan información adicional acerca de la estructurta del semigrupo A una relación de equivalencia R en el semigrupo (S,*) se le llama RELACIÓN DE CONGRUENCIA si a R a’

y

bR b’ implica (a*b) R (a’*b’)

Ejemplo # 1: Examínese el semigrupo (Z,+) y la relación de equivalencia R en Z definida por a R b sí y sólo si 2 divide a a-b conde se denotó a R b por a=b (mod 2) Ahora se demostrara´ que ésta relación es un relación de congruencia como sigue. Si

Lic. GUILLERMO MAS AZAHAUNCHE

410

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

a=b (mod 2)

c=d (mod 2)

entonces, 2 divide a a-b y 2 divide a c-d,por lo cual a-b= 2m

y

c-d= 2n

donde m y n están en Z, se tiene ( a-b) +(c-d)=2m + 2n o bien ( a-b) +(c-d)=2(m +n) por lo tanto se tiene a + c= b + d (mod 2) Ejemplo # 2: Examínese el semigrupo (ℤ,+), donde + es la adición ordinaria. Sea: f(x)=x2- x-2-.Ahora se definirá la siguiente relación en Z: a R b sí y sólo si f(a)=f(b)

¿Analizar se R es una relación de congruencia?

Solución Se verifica directamente que R es una relación de equivalencia en Z. Sin embargo, R no es una relación de congruencia ya que se tiene -1 R 2 (f(-1)=f(2)=0) y -2 R 3 (f(-2)=f(3)=4) Para que sea una Relación de Congruencia se debe cumplir: Si -1 R 2

y

-2 R 3

Pero como f(-3)=10

entonces ( - 1, -2 ) R ( 2 , 3) osea f ( -3) debe ser igual a f ( 5 ) y f (5)=18 f ( -3) ≠ f ( 5 ). Luego no existe congruencia.

TEOREMA 2: Sea R una relación de congruencia en el semigrupo Examínese la relación

(S,*).

de S/R x S/R en S/R en que el par ordenado está, para a

y b en S, relacionado con ([a * b]).

Lic. GUILLERMO MAS AZAHAUNCHE

411

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

(a)

es una relación de S/R x S/R en S/R y es común denotar a ([a], [b]) como [a]

[b]. Por consiguiente, [a]

[b]=[a * b].

(b) (S/R, ) es un semigrupo. Demostración. Supóngase que ([a], [b])=.([a’], [b’]).Así, a R a’ y b R b’,por lo cual se deberá tener a * b R a’ * b’ ,ya que R es una relación de congruencia. Por consiguiente, [a * b]= [a’ * b’]; esto es,

es una función. Esto significa que

es

una operación binaria en S/R. Luego se verificará que

es una operación asociativa. Se tiene

[a] ( [b] * [c])= [a] [b * c] = [a * (b * c)] = [(a * b )* c] (por la propiedad asociativa de * en S) = [a * b] [c] = ([a ] [b]) [c] De aquí ,S/R sea un semigrupo cociente o el semigrupo factor COROLARIO 1: Sea R una relación de congruencia en el monoide (S,*).Se define la operación en S/R por [a] [b]=[a * b] entonces (S/R, ) es un monoide. Demostración. Si el idéntico en (S,*),entonces es fácil verificar que [e] es el idéntico en (S/R, ). Ejemplo # 3: Se define la siguiente relación en el semigrupo (Z,+). a R b sí y sólo si n divide a a-b Se demostrará que R es una relación de equivalencia con n=2 ,R se escribirá =(modn).Por consiguiente si n=4,entonces 2=6 (mod 4) Ya que 4 divide a (2-6).Se al lector demostrar que =(mod n) es una relación de congruencia en Z.

Lic. GUILLERMO MAS AZAHAUNCHE

412

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Ahora sea n=4 y se calcularán las clases de equivalencia determinadas por la relación de congruencia =(mod 4) en Z.Se obtiene [0] = {...,-8,-4,0,4,8,12,...} =[4]=[8]=... [1] = {...,-7,-3,1,5,9,13,...} =[5]=[9]=... [2] = {...,-6,-2,2,6,10,14,..}.=[6]=[10]=... [3] = {...,-5,-1,3,7,11,15,...}=[7}=[11]=... Estas son todas las clases de equivalencia que forman el conjunto cociente Z/=(mod 4).Se acostumbra denotar al conjunto cociente Z/=(mod n) como Zn;Zn es un monoide con la operación ⊕ y el idéntico [0].Ahora se determinará la tabla de adición para el semigrupo Z4 con la operación ⊕ ⊕ [0] [1] [2] [3] [0] [0] [1] [2] [3] [1] [1] [2] [3] [0] [2] [2] [3] [0] [1] [3] [3] [0] [1] [2] Los componentes de ésta tabla se obtienen de la ecuación [a] ⊕ [b]= [a+b] Por consiguiente [1] ⊕ [2]= [1+2]=[3] [1] ⊕ [3]= [1+3]=[4]=[0] [2] ⊕ [3]= [2+3]=[5]=[1] [3] ⊕ [3]= [3+3]=[6]=[2] se puede demostrar que Zn tiene n clases de equivalencias [0],[1],[2],...,[n-1] y que [a] ⊕ [b]=[r] donde r es el residuo de dividir a+b entre n. Por consiguiente, si n=6 [2] ⊕ [3]=[5] [3] ⊕ [5]=[2] Lic. GUILLERMO MAS AZAHAUNCHE

413

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

[3] ⊕ [2]=[0] A continuación se axaminará la conexión entre la estructura del semigrupo (S,*). y el semigrupo cociente (S/R, )., donde R es una relación de congruencia en (S,*). GRUPOS Condiciones: (G; ) 1)  es cerrada en G 2)  es asociativa en G. a  (b  c) = (a  b)  c para cualesquiera a,b,c de G 3) ∃ e neutro en G para  : En A existe un elemento denotado por 1 que cumple 1 a = a  1 = a (elemento neutro) 4) ∃ a’ para cada a de G / a’ a = a a’ = e (a’es elemento inverso) Cuando además de ser grupo la operación es conmutativa, se dice que es Grupo Abeliano. En otras palabras, un grupo es un conjunto con una operación binaria asociativa, cerrada, que posee inversos y elemento neutro. Un grupo donde se verifique a  b = b  a para cualquier par de elementos a,b en G se dice abeliano o conmutativo. Ejemplos:  (R,+) es grupo abeliano. R es el conjunto de los números reales y + la

suma usual.  (R-{0},·) es grupo abeliano. (Notar que el cero no tiene inverso

multiplicativo, por eso se lo excluye).  (Zn,+) es grupo.

Un grupo es finito o infinito si el conjunto es finito o infinito. En nuestro ejemplo, los formados con R son infinitos y el formado con Z n es finito. Composición de funciones:

Lic. GUILLERMO MAS AZAHAUNCHE

414

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Es asociativa, generalmente no es conmutativa. El elemento neutro es la Identidad. La función inversa es la que conocemos habitualmente y decimos que la composición de F con G es otra función de pares (x,y) / ∃ k: (x,k) ∈ g ∧ (x,y) ∈ F. Ejemplo: A

F1

F2

F3

F4

F5

F6

1

1

2

3

1

2

3

2

2

3

1

3

1

2

3

3

1

2

2

3

1 •

 La operación es cerrada, como se puede observar en la tabla.  La composición de funciones es asociativa.  F1 es la identidad y funciona como neutro.  Cada elemento tiene inverso.  No es conmutativa, puesto que F4° F3 = F5 y F3° F4 = F6, por lo tanto (F; ° ) es grupo no abeliano. Inversos: F1’ = F1

F4’ = F4

F2’ = F3

F5’ = F5

F3’ = F2

F6’ = F6

SUBGRUPOS Si un conjunto S ≠ ∅ , incluido en G, tiene a su vez estructura de grupo, decimos que S es un subgrupo de G. En el ejemplo anterior S = { F1, F2, F3} , constituye a su vez un grupo, además abeliano. Nótese que todo grupo abeliano tiene todos sus subgrupos abelianos, sin embargo un grupo no abeliano puede tener grupos abelianos o no abelianos.

Lic. GUILLERMO MAS AZAHAUNCHE

415

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

El Conjunto generado por un elemento es el conjunto que se obtiene operando un elemento consigo mismo como sea necesario hasta que empieza a repetirse. < F1> = { F1}

< F4> = { F1; F4}

< F2> = { F3; F1; F2}

< F5> = { F1; F5}

< F3> = { F2; F1; F3}

< F6> = { F1; F6}

Todo conjunto tiene como mínimo dos subgrupos: el Subgrupo Trivial { e} y el Subgrupo Impropio, que es G. Cualquier subgrupo que no sea el trivial ni el impropio se denomina Subgrupo Propio. Teorema de Lagrange Si un conjunto es finito, de cardinal n y tiene un subgrupo de cardinal d, entonces d divide a n. En consecuencia si el cardinal de un grupo es primo, no tiene subgrupos propios. Grupos de pocos elementos a) Grupos de un elemento: El único grupo de un elemento es el grupo trivial (neutro). b) Grupos de dos elementos: 

e

a

e

e

a

a

a

e

Cualquier conjunto que contenga al neutro y a otro elemento inverso de si mismo es subgrupo del dado. c) Grupos de tres elementos: 

e

a

b

e

e

a

b

a

a

b

e

b

b

e

a

Lic. GUILLERMO MAS AZAHAUNCHE

416

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Si queremos encontrar grupos de tres elementos debemos buscar dos elementos que sean uno inverso del otro y que además el primero operado con si mismo de el segundo y viceversa. d) Grupos de cuatro elementos: 

e

a

b

c

e

e

a

b

c

a

a

e

c

b

b

b

c

a

e

c

c

b

e

a

Si el subgrupo de cuatro elementos tiene un inverso de si mismo y una pareja, debemos comprobar que b  b = c  c = a Grupos Cíclicos Decimos que un grupo es Cíclico cuando hay por lo menos un elemento que genera todo el grupo. Los grupos cíclicos son siempre conmutativos. El ejemplo de las funciones no es cíclico, porque no existe elemento que genere a todos. Ejemplo: (ℤn; ⊕ ) a) Por definición la suma de clases es otra clase, por lo tanto es cerrada. b) La suma de clases es asociativa y conmutativa porque lo es la suma en Z. c) La clase del cero funciona como elemento neutro en base a la definición dada. d) Cada clase x tiene su inverso en la clase n-x e) Para cualquier n, (Zn; ⊕ ) es un grupo abeliano. En todos los casos el elemento 1 genera a todos los demás, por lo tanto son grupos cíclicos. ≡ 12

2’ = 10

5’ = 7

0’ = 0

3’ = 9

6’ = 6

1’ = 11

4’ = 8

Lic. GUILLERMO MAS AZAHAUNCHE

417

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Los números coprimos con n generan todo el conjunto. Los divisores de n generan al conjunto de sus múltiplos que constituyen subgrupos. En las clases Zn con el producto de clases, debemos retirar la clase del 0, que es absorbente para el producto, si n es un número primo entonces (Zn -{ 0} ; ⊗ ) tiene estructura de grupo. El elemento neutro es la clase del 1 y los inversos los encontramos en la tabla correspondiente. En Zn con el producto cuando n no es primo, veremos que algunos elementos tienen inversos. El conjunto de estos elementos es con el producto un grupo abeliano. Si un grupo tiene cardinal infinito para probar que es un subconjunto es subgrupo de él, debemos probar que la operación es cerrada, que existe neutro y que cada elemento tiene inverso. Si el cardinal del grupo es finito, para probar que un subconjunto es subgrupo basta mostrar que la operación es cerrada en él. Ejemplo: { Z14 -{ 0} ; ⊗ } INV = { 1,3,5,9,11,13} •

1

3

5

9

11

13

1

1

3

5

9

11

13

3

3

9

1

13

5

11

5

5

1

11

3

13

9

9

9

13

3

11

1

5

11

11

5

13

1

9

3

13

13

11

9

5

3

1

1’ → 1

2’ → No

Lic. GUILLERMO MAS AZAHAUNCHE

418

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS 3’ → 5

4’ → No

7’ → No

9’ → 11

13’→ 13 Subgrupos: { 1;13}

{ 1;3,5} → No válido

{ 1;9,11}

{ 1}

Intersección de subgrupos: 1) Sean H1 y H2 elementos pertenecientes a la intersección de h y k. eso significa que ambos pertenecen a H, que por ser subgrupo contiene a H1 con H2. 2) Por pertenecer ambos a la intersección, pertenecen a k, y como k es un subgrupo contiene a H1  H2. Por pertenecer H1  H2 a ambos conjuntos pertenece a la intersección. El neutro pertenece a ambos subgrupos, por lo tanto pertenece a la intersección. 3) La asociatividad se hereda de un grupo grande a cualquier conjunto, y por lo tanto a la intersección. 4) Si H pertenece a la intersección es porque pertenece a H grande, que por ser subgrupo contiene a H’; pero H pertenece también a k, que por ser subgrupo contiene a k’; entonces k’ por pertenecer a h y k pertenece a la intersección. Congruencia Módulo H Dado un grupo G, y un subgrupo H de él, definimos la relación Congruencia Módulo H en G de la siguiente manera: a ≡ h b ⇔ a’  b ∈ H ∀ a, b ∈ G Congruencia modulo H a izquierda. a ≡ h b ⇔ a  b’ ∈ H ∀ a, b ∈ G Congruencia modulo H a derecha. a) a ≡ h a a’  a = e ∈ H Es reflexiva b) a ≡ h b ⇒ a’  b ∈ H ⇒ (a’  b’) ∈ H ⇒ b’  (a’)’ ∈ H ⇒ b’ a ∈ H ⇒ b ≡ h a c) a ≡ h b ⇒ a’  b ∈ H b ≡ h c ⇒ b’  c ∈ H Lic. GUILLERMO MAS AZAHAUNCHE

419

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Queda demostrado que ≡ h es de equivalencia, por lo tanto produce en G una partición en clase de equivalencia. La clase del neutro es el subgrupo H, porque ∀ elemento de H ° e es un elemento de H. La partición que produce es regular, por lo tanto, cada clase tiene tantos elementos como el subgrupo H, si G ≠ ∞ , de # n y H tiene # q ⇒ la cantidad de clases de equivalencias es n/q, y el índice del subgrupo se obtiene efectuando # G / # H. Homomorfismos Sean dos grupos G, G’, decimos que f, definida en G → G’ es un Homomorfismo ⇔ f (a  b) = f (a)  f(b). Si f es sobreyectiva es un Epimorfismo. Si f es inyectiva, entonces es un Monomorfismo. Si f es biyectiva es un Isomorfismo. Si está definido un grupo en ese mismo grupo es un Endomorfismo, y si además es biyectiva, es un Automorfismo.

EJERCICIOS DE APLICACIÓN a c 1. Sea el semigrupo Q , + con b R d ⇔ ad = bc

(

)

equivalencia

(Q , + ) es de A = {1 , 2 , 3 , 5 , 7 , 9 } mediante la

2. Dada la operación * definida en el conjunto tabla de doble entrada: * 1 2 3 1 1 2 3 2 2 3 1 3 3 2 5 5 5 1 3 7 7 5 3 9 9 5 1 Analizar si la operación * es: a) De Clausura b) Idempotente c) Conmutativa d) Si existe elemento neutro e) Si existe elemento inverso

Lic. GUILLERMO MAS AZAHAUNCHE

¿Probar que

5 5 1 7 4 3 7

7 7 4 1 1 7 1

9 9 1 7 5 9 3

420

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

3.- Sea G = { e , a , b , c , d , f , g , h } un grupo abeliano de 8 elementos en el que todo elemento, salvo la identidad, es de orden 2, y tal que:

d f =a

dg =b ; dh=c ;

;

f g =c ;

f h=b

; g h = a . Estas

relaciones son suficientes para que usted escriba la tabla del grupo. Diséñela.

{

}

{

}

4.- Dados los conjuntos: A = 1 , 2 ,3 , ∧ B = a , b, c se define las operaciones binarias: * y % en los conjuntos A y B respectivamente mediante: * 1 2 3 Si f(1) = b f(2) = a 1 1 2 3 f(3) =c 2 2 3 1 3 3 1 2 ¿Analizar si A , * ∧ B ,% son isomorfos?

(

)

(

% a b c

)

5.- Definimos la operación * mediante la propiedad:

a c a b

b a b c

C b c a

a∗b = a + b − 2ab.

Analizar si la operación es: a) Idempotente b) Conmutativa c) Asociativa d) Si existe el elemento neutro e) Determinar si existe el inverso

(

)

(

)

6.- Consideremos las estructuras Z + ,+ en Z + , ⋅ y f : Z + → Z + / f x = 2 2 x ¿Es un homomorfismo de Z + ,+ en Z + , ⋅ ? 7.- Que axiomas se deben cumplir para que G sea un anillo conmutativo?

()

8.- Dado el triángulo dado en la figura dada Donde las funciones de permutación son: 1 2 3   1 2 3  , f2 =   , f1 =  1 2 3   2 3 1    

1 2 3  f3 =  3 1 2  

1 2 3   1 2 3  , g2 =   g1 =  1 3 2  3 2 1    

 1 2 3  g3 =   2 1 3  

,

(

)

(

)

Representar la operación ∗ sobre el conjunto S 3 = f 1 , f 2 , f 3 , g1 , g 2 , g 3 mediante una tabla de multiplicar

{

}

Lic. GUILLERMO MAS AZAHAUNCHE

421

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

9.- En

R × R* Demostrar

( x , y )∗ ( z , t ) = ( y z + x , y t ).

se define la siguiente ley *:

(R × R ,∗) *

es un grupo no abeliano.

TABLAS Y MAQUINAS DE ESTADO FINITO El tema que a continuación vamos a ver es muy importante para entender y razonar el trayecto de cómo se manipulan las cadenas o palabras en un programa de conmutación. Este tema va servir de modelo para realizar los siguientes puntos de los siguientes capítulos del libro de matemáticas discretas, pero también nos va a servir para aprender mas de lo que es una base de datos, tenemos en cuenta que una base de datos esta compuesta por un conjunto de tablas en el cual una tabla o registro es un conjunto de campos y todos esto vendría a ser un archivo, para luego descubrir que un campo es un conjunto de cadenas o palabras que tienen un valor clave en la base de datos para luego relacionarlas con formularios, consultas, vistas, etc., que son propiamente dadas por una base de datos.

Pero en este tema nos va a interesar cono sé interactúan las palabras o cadenas de una máquina empleando el razonamiento inverosímil del propio programa que se encarga de avisar con mensaje al computador en base de semigrupos. SEMIGRUPOS, MÁQUINAS Y LENGUAJES. Sea M = (S,I,F) una máquina de estado finito con conjunto de estados S={S0, S1...,Sn}, conjunto de entrada I y funciones de transición de estados

F={fx | x ∈I}. Se asociará a M dos monoides, cuya construcción se recordará de la sección 9.2. En primer lugar se encuentra el monoide libre I* sobre el conjunto de salidas I. Este monoide consta de todas las secuencias finitas (“cadenas” o “palabras”) de I, con la concatenación como operación binaria. La identidad es la cadena vacía Λ. En segundo lugar, se tiene monoide Ss, que consta de todas las funciones de S en S, con la composición de funciones como operación binaria. La identidad de Ss es la función 1s dada por 1s (s) = s, para todas en s en S.

Lic. Guillermo Mas Azahuanche

422

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Si w= x1x2...xn E I* , sea fw = fxn ° fxn-1 °...° fx1, la composición de las funciones fxn, fxn-1, ...,fx1.Tambien se define fΛ como 1s. De esta forma, se asigna un elemento

fw de Ss con cada elemento w de I*. Si se piensa cada fx como el efecto de la entrada x sobre los estados de la maquina M, entonces fw representa el efecto combinado de todas las letras de entradas sobre la palabra w, recibidas en el orden especificado por w. Se dice que fw es la función de transición de estados correspondiente a w. Ejemplo 1.

Sea M = (S,I,F), donde S=[ s0,s1,s2], I=[0,1] y F esta dada por la

siguiente tabla de transición de estados. 0

1

s0

s0

s1

s1

s2

s2

s2

s1

s0

Sea w = 011 E I*. Entonces Fw (so) = (f1 ° f1 ° f0)(S0) = f1( f1( f0(s0))) = f1( f1( s0)) = f1(s1) =s2. De manera análoga, Fw (s1) = f1( f1 (f0( s1))) = f1 (f1 (s2)) = f1 (s0) = s1 Fw (s2) = f1 (f1 (f0(s2))) = f1 (f1 ( s1) ) = f1 ( s2) = s0.

Y

Ejemplo 2. Considérese la misma maquina M del ejemplo 1 y examínese el problema de calcular fw de manera un poco distinta. En el ejemplo 1, se usa la definición de manera directa, y para una maquina de gran tamaño se programaría un algoritmo para calcular los valores de fw justo de esa forma. Sin embargo, si la maquina tiene un tamaño moderado, tal vez sea preferible otro procedimiento. Se comenzaría por trazar el digrafo de la maquina M como en la figura 1.Se utiliza este digrafo para calcular las funciones de transición entre las palabras siguiendo

las aristas correspondientes a las transiciones de las letras de

entrada. Así para calcular fw(s0), se comienza en el estado s0 y se observa que la entrada 0 lleva al estado s0. La entrada 1 siguiente lleva al estado s1, y la

entrada final de 1 lleva a s2. Así, fw(s0) =s2, como antes.

Lic. Guillermo Mas Azahuanche

423

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

0 1

S0

S1 1

0,1

S2

0

Calcúlese fw’, donde w’ = 01011. Las transiciones sucesivas de S0 son 0 1 0 1 1 S0  S0  S1  S2  S0  S1, De modo que fw’(S0)= S1. Un análisis similar muestra que fw’(S1)= S2 y fw’(s2)=S0. Este método de interpretación de las funciones de transición de palabras como fw y fw’ es útil al diseñar máquinas que tienen transiciones de palabra con ciertas propiedades deseadas. Este es un paso crucial en la aplicación práctica de la teoría, y será considerado en la siguiente sección. Sea M=(S,I,F) una máquina de estado finito. Se define una función T de I* en Ss. Si w es una cadena en I*, sea T(w)= fw como se ha definido anteriormente. Entonces, se obtiene el siguiente resultado. Teorema 1. (a) Si w1 y w2 están en I*, entonces T(w1.w2)= T(w2) o T(w1). (b) Si M= T(I*), entonces M es un submonoide de Ss. Demostración: (a) Sean w1= x1x2......xk y w2= y1y2....ym dos cadenas en I*. Entonces T(w1.w2)= T(x1x2....xky1y2...ym)= (fym o fym-1 o.....o fy1)o (fxk o fxk-1 o.....o fx1)= T(w2) o T(w1). Además, por definición, T(Λ)= 1s. Así, T es un homomorfismo de monoides. (b)La parte (a) muestra que si f y g están en M, entonces f o g y g o f están en M. Así, M es un subsemigrupo de Ss. Como 1s= T(Λ), 1s ∈ M. Así, M es un submonoide de Ss. El monoide M es el monoide de la máquina M.

Lic. Guillermo Mas Azahuanche

424

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Ejemplo 3. Sea S={ S0, S1, S2} e I= {a,b,d}. Considere la máquina de estado finito M= { S,I,F} definida mediante el digrafo de la figura 2. Calcule las funciones fbad’ fadd y fbadadd y verifique que: a, b

fadd o fbad = fbadadd b

a

d

a

S0

S1

S2

d Solución:

b, d

Se calcula fbad mediante la siguiente serie de transiciones: b So

a

d

S0 b

S0 a

S1

S1 b S2

S1 d

S2

S1

a S1

d S2

S1.

Así, fbad (s0)= s1, fbad(s1)= s1 y fbad (s2)= s1. De manera que análoga, para fadd’ a d S0

S0 a

S1

S0

d S2

S1

d

a

d S1

S0

d

d

S2 S1 S0’ S2 De modo que fadd(si)= s0 para i=0,1,2. Un cálculo similar muestra que Fbadadd(S0) = S0’

fbadadd(S1) = S0’

fbadadd(S2) = S0

Las mismas fórmulas son válidas para fadd o fbad. De hecho, (fadd o fbad) (S0) = fadd(fbad(S0)) = fadd (S1) = s0 (fadd o fbad) (S1) = fadd (fbad (S1)) = fadd (S1) = s0 (fadd o fbad) (S2) = f add (fbad (S2)) = fadd (S1) = s0.

Ejemplo 4. Considere la máquina cuya gráfica aparece en la figura 10.35. Muestre que fw(s0) = s0 si y sólo si tienen 3n unos para algún n > 0.

Lic. Guillermo Mas Azahuanche

425

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

0

0

1

S0

1

S1

1

S2

0 Solución: De la figura 10.35, se observa que f0 = 1s’ de modo que los ceros en una cadena w e I* no influyen sobre fw’. Así si w es w con todos los ceros eliminados, entonces fw = fw. Sea l(w) la longitud de w, es decir, el número de dígitos en w. Entonces l( w ) es el número de unos en w E I*. Para cada n > 0, considere la proposición:

P(n): Sea w e I* y sea l(w)=m. (a) Si m = 3n, entonces fw(s0) = s0. (b) Sí m = 3n + 1, entonces f w(s0) = s1. (c) Si m = 3n + 2, entonces fw(s0) = s2.

Se demostrará por inducción matemática que P(n) es verdadera

∀n>0

Paso Básico. Sea n=0. En el caso (a), m=0; por lo tanto, W no tiene unos y FW(S0)=1S(S0)=S0. En el caso (b), m=1, de modo que w = 1 y fw(s0)=fw(s0)=f1(s0)=s1. Por último, en el caso ( c ), m=2 de modo que W=11 y fw (s0)

= fw (s0) =

f

11(s0) =f1(s1)=s2

Lic. Guillermo Mas Azahuanche

426

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Paso Inductivo. Se debe mostrar que P(k) P(k+1) siempre es verdadero. Supóngase que P(k) es verdadero para alguna k>0. Sea w e I*, y se denota l(w) por m. En el caso (a), m=3(k+1)=3k+3; por lo tanto w=w’ 111, donde l(w’)=3k. Entonces fw(s0)=S0 por la hipótesis de inducción, y f111(s0) por cálculo directo,de modo que fw(s0)= fw’(f111(s0))=fw’(s0)=s0. Los casos (b) y (c) son analizados de igual manera. Así, P(k+1) es verdadero. Por inducción matemática P(n) es verdadero para toda n>0, de modo que fw(s0)=S0 si y sólo si el número de unos en w es múltiplo de 3. Ejemplo 5. Sea M=(S, I;F, s0;T) la máquina de Moore donde (S, I, F) es la máquina de estado finito cuyo digrafo aparece en la figura 10.35 y T={s1}. El análisis del ejemplo 4 muestra que fw(s0)=s1 si y sólo si el número de unos en w es de la forma 3n+1 para alguna n>0, así, L(M) es precisamente el conjunto de todas las cadenas con 3n+1 unos para alguna n>0. Ejemplo 6. Considere la máquina de Moore cuyo digrafo aparece en la figura 10.35. En este caso, s0 es el estado inicial, y T={S2}. ¿Qué es L(M)? Es claro que el conjunto de entradas es I={a,b}. Observe que, para que una cadena w provoque una transición de s0 a s2’ w debe contener al menos dos b. Después de alcanzar a s2’ cualquier letra adicional no tiene efecto alguno. Así, L(M) es el conjunto de cadenas con dos o más b. Por ejemplo, se observa que faabaa(s0)=s1’ de modo que aabaa es rechazada. Por otro lado fabaab(s0)=s2’ de modo que abaab es aceptada.

a.

a

S0

b

a, b

S1

b

S2

MAQUINAS DE ESTADO FINITO: Son modelos abstractos de máquinas con una memoria interna primitiva. Un autómata de estado finito es un tipo particular de máquina de estado finito que está íntimamente ligada a u tipo particular de lenguaje. Lic. Guillermo Mas Azahuanche

427

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Sea M = (S , I , F ) una máquina de estado finito con conjunto de estados: S = {S 0 , S1 ,, S n }, conjunto de entrada I y funciones de transición de estados F = { f x / x ∈ I }. Se asociará a M dos monoides, cuya construcción se ha visto anteriormente. En primer lugar se encuentra el monoide libre I * sobre el conjunto de salidas I. Este monoide consta de todas las secuencias finitas (“cadenas” o palabras) de I, con la concatenación como operación binaria. La identidad es la cadena vacía Λ. En segundo lugar, se tiene el monoide S * , que consta de todas las funciones de S en S, con la composición de funciones como operación binaria. La identidad de S * es la función I S dada por I S (S ) = S , para todas de en S en . * Si w = x1 x 2  x n ∈ I , sea f w = f xn  f xn −1    f x1 la composición de

las funciones f xn , f xn −1 ,  , f x1 también se define f Α como I S . De esta forma, se s asigna un elemento f w de S con cada elemento de w de I * . Si se piensa cada

f x como efecto de la entrada x sobre los estados de la máquina M, entonces

f w representa el efecto combinado de todas las letras de entradas sobre la palabra w, recibidas en el orden especificado por w. Se dice que f w es la función de transición de estados correspondiente a w

Máquinas de Turing En 1936, Alan Turín contestó a la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles,es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. En el artículo On Computable Numbers, Turing construyó un modelo formal de computador, la Máquina de Turing, y demostró que había problemas tales que una máquina no podía resolver. La máquina de Turing es el primer modelo teórico de lo que luego sería un computador programable. Con el tiempo a este tipo de máquina se la conoció como máquina de estado finito, debido a que en cada etapa de un

Lic. Guillermo Mas Azahuanche

428

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

cálculo, la siguiente acción de la máquina se contrastaba con una lista finita de instrucciones de estado posibles.

Definición. Una máquina de Turing es una máquina idealizada para el procesamiento de información, cuyas acciones están especificadas en términos matemáticos. En definitiva, es un dispositivo que lleva a cabo un procedimiento de cálculo definible en términos finitos. Es un elemento de “matemática abstracta”, y no un objeto físico. Descripción. La máquina de Turing consiste de: - Una cinta ilimitada por sus dos lados, y dividida en células. - Un número finito de signos s1, s2 ,...sh , que forman el alfabeto exterior, en el que se cifran los datos introducidos en la máquina y los datos finales de la máquina. Estos signos se introducen en las células; entre ellos se encuentra el signo vacío , s1 = Λ, que borra el signo que había antes en una célula, y deja la célula vacía. Como máximo puede haber un signo exterior en cada célula

- Un número finito de estados internos diferentes, que se representarán por q1 , q2 , ... , qm - La Unidad Lógica tiene dos canales de entrada; por uno de ellos entra el dato externo que lee en la cinta, y por el otro el estado interno en el que está la máquina. - Después de observar una célula de la cinta de datos, la Unidad Lógica sustituye el símbolo observado si por otro signo sj. Si i=j , la célula no cambia; si i=1, se borra lo que había en esa célula. - El funcionamiento de la máquina se realiza en unidades consecutivas de tiempo. Cuando se pasa de una unidad de tiempo a la siguiente, la dirección de la célula observada puede cambiar en no más de una unidad; es decir, se contemplará la vecina de la derecha (D), la vecina de la izquierda (I), o la misma célula del tiempo anterior (M). - La Unidad Lógica tiene tres canales de salida: El primero para la salida de la cinta donde se ha modificado el dato de entrada si; el segundo indica el estado Lic. Guillermo Mas Azahuanche

429

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

interno en el que debe situarse la máquina, qi ; el tercero para indicar cuál será el siguiente dato a leer de la cinta de entrada, D, I ó M. - Los signos D, M, I, q1 , q2 , ... , qm , constituyen el alfabeto interno de la máquina. - Dependiendo de los datos iniciales puede ocurrir: a) Después de un número finito de tiempos, la máquina se para; en este caso se dice que la máquina es utilizable para la información inicial.

b) La información de parada no aparece; en este caso se dice que la máquina no es utilizable para la información inicial.

Se dice que la máquina resuelve cierta clase de problemas, si siempre es utilizable para la información de cada problema de ese tipo.

En cada instante de tiempo, la máquina: 1º Lee la entrada de la cinta y Lee el estado interno en que se encuentra 2º Cambia la entrada de la cinta, Cambia el estado interno e Indica hacia dónde mover la cinta

Un esquema funcional de lo que sería una máquina de Turing nos lo da el siguiente ejemplo:

Supongamos que la máquina está en un estado interno inicial q1 , y que se dispone a leer el segundo de cinco “unos” consecutivos, introducidos en la cinta como datos de entrada iniciales. El funcionamiento de la máquina sería el siguiente:

Lic. Guillermo Mas Azahuanche

430

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Se observa que la parada de la máquina tendrá lugar bajo las condiciones de que en cierta etapa del proceso surja el estado q5, que representa el estado de parada.

Para simplificar la tabla, acordamos que cuando los signos de entrada no se diferencian de los de salida, por comodidad de notación pueden omitirse en la tabla. También se omitirá el signo M que indica la falta de movimiento de la cinta; esto permite omitir por completo la última columna del último ejemplo, que corresponde al estado de parada. El estado de parada se notará por !

Veamos algún ejemplo de cómo construir máquinas de Turing que realicen algunos algoritmos aritméticos sencillos. Problema. ¿Cuál es el resultado obtenido por la máquina 1 cuando actúa sobre 3592, 389, 99, desde el estado q0 situado en el último dígito? ¿y cuando actúa sobre 3592 / , 389 / / / / / , 99 / / , desde el estado q1 situado en la última barra? ¿Cuál crees que es el objetivo de la máquina 1 ? Máquina 1. Alfabeto exterior = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Λ, / } Estados internos = {q0, q1, !}

Ejercicios Propuestos 1.

Sea M = (A, S, Z, F, G) una máquina de estado finito con alfabeto de entrada A = { + , x} , conjunto de estados S = { so , s1 , s2 } , alfabeto de salida Z = {0,1} y funciones F de estados y G de salida definidas por la tabla de estados: Lic. Guillermo Mas Azahuanche

431

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

S

F + s1 s2 s1

so s1 s2

x s2 s1 s0

G + 1 0 1

x 0 1 0

Si el estado inicial es so : a) b)

2.

Representar la máquina M mediante un diagrama. Si la cadena de entrada es: + xx + x ++ x , encontrar la cadena de salida y la cadena de estados.

Dadas las siguientes máquinas de estado finito: M S S1 S2 S3 S4 S5 S6

F 0 S2 S1 S2 S6 S2 S4

1 S3 S5 S5 S3 S3 S5

G 0 0 1 1 0 1 1

M’ S’ T1 T2 T3 T4

1 1 0 1 1 1 0

F’ 0 T2 T1 T2 T2

1 T3 T4 T4 T3

G’ 0 0 1 1 0

1 1 0 1 1

a) Hacer los diagramas correspondientes a cada una de las máquinas b) Establecer una función suryectiva que permita que la máquina M’ cubra a la máquina M y luego probar que la función encontrada es en realidad un cubrimiento. 3. Minimizar la máquina M = (A, S, Z, F, G) con alabeto de entrada A = {a,b,c} , conjunto de estados S = {1,2,3,4,5,6,7,8}, alfabeto de salida Z = {0,1,*} y funciones F, de estados, y G, de salida, definidas por la tablas: M F G S a b c a b c 1 3 8 2 * 1 0 2 7 5 3 0 * 1 3 1 7 5 * 1 0 4 4 8 2 * 1 0 5 8 2 1 0 * 1 6 5 6 7 * 1 0 7 5 8 6 0 * 1 8 2 7 6 0 * 1 4.

Dada la máquina de estados finitos: M S 0 1 2

a 2 2 2

Lic. Guillermo Mas Azahuanche

F b 2 2 3

c 7 6 2

a 0 1 1

G b 0 1 1

c 0 0 0 432

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

3 4 5 6 7 8 9

2 8 5 4 7 5 9

2 6 5 1 7 5 7

3 8 8 4 9 8 9

1 0 1 0 0 1 0

1 0 1 0 0 1 0

0 1 0 1 0 0 0

Hallar M la máquina mínima de M y encontrar la función que define el cubrimiento de M por M . 5.

Sea M una máquina de estados finitos definida por : M S 0 1 2 3 4 5 6 7 8 9 10

F b 0 2 0 5 4 9 6 4 6 1 1

a 0 1 0 7 4 3 6 4 8 1 1

c 0 1 1 7 7 3 8 7 8 5 6

a 0 0 0 1 0 1 1 0 1 0 1

G b 0 0 0 1 0 1 1 0 1 0 1

c 1 1 1 0 1 0 1 1 1 1 1

Encontrar M , la máquina mínima de M y hallar la función que define el cubrimiento de M por M . 6.

Hallar la función que define el cubrimiento entre la siguiente máquina y su máquina mínima.

M S 0 1 2 3 4 5 6 7 8 9

7.

F a 0 2 0 5 4 9 6 4 6 9

G b 0 1 1 3 7 3 8 7 8 5

a 1 1 1 0 1 0 0 1 0 1

b 0 0 0 1 0 1 0 0 0 0

Dada la máquina de estados finitos: Lic. Guillermo Mas Azahuanche

433

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

M S 1 2 3 4 5 6 7 8 a) b) c) d) 8.

a) b)

9.

F b 4 6 7 1 5 7 6 7

a 6 8 3 7 4 4 1 2

c 2 4 1 8 6 5 5 1

a + * * + * + + *

G b * x x * x * * x

c x + + x + x x +

Encontrar la partición correspondiente a la relación de 2-equivalencia en el conjunto de estados. Encontrar la partición correspondiente a la relación de 5-equivalencia en el conjunto de estados. Hallar M la máquina mínima de M . Hallar una función que defina el cubrimiento de M por M . Demostrar que la relación de cubrimiento de máquinas es reflexiva y transitiva. Demostrar que la equivalencia de máquinas es una relación de equivalencia.

Dadas las máquinas de estados finitos M1 y M2 : M1 S1 a b a) b)

F1 0 a b

G1 1 b a

0 0 0

1 1 1

M2 s2 x y

F2 0 y x

G2 1 y x

0 0 0

1 1 1

Demostrar que M1 y M2 son equivalentes . Demostrar que M1 y M2 no son isomorfas .

10. Determine: a) El conjunto finito A de símbolo de entrada. Un conjunto finito S de estados internos. Un conjunto finito Z de símbolos de δ 0 salida. b) La tabla que define las funciones de estado siguiente y de salida de la máquina de estado finito descrito en forma gráfica de la máquina de b/ 1 la figura .

a/ 0 δ

1

a/ 1 b/ 0

a/ 0 b/ 0

c) Determine la cadena de salida para la cadena de entrada: Bbababbabaaa. En forma recursiva para la máquina dada en la parte (b)

δ

δ

2

a/ 0

11.- Si se da la tabla de una máquina de estado finito: Lic. Guillermo Mas Azahuanche

434

3

b/ 0

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Estado presente S0 S1 S2 S3

S4 S5

Entrada Salida 0 1 0 1 S5 S3 0 1 S1 S 4 0 0 S3 0 S1 0 S1 S 2 0 0 S5 S 2 0 1 S1 0 1 S4

Se pide: a) Describa el estado finito de la máquina en forma gráfica. b) Encuentre la máquina equivalente. c) Describa el estado finito de la máquina equivalente en forma gráfica.

k +1

k

/ S j si solo si S i ≅ S j para todo Sug. Use el teorema: Sea s i , s j ∈ S . Entonces S i ≅ a ∈ I ; f (si , a ) ≅ f (s j , a ) . Use: S 0′ ≅ S 0 ≅ S 4 , S 4′ ≅ S 5 , S 3′ = S 5 . La máquina equivalente será de cuatro salidas. k

S 2′ ≅ S 2 ≅ S 3 ,

12. Determine: a) El conjunto finito A de símbolo de entrada. Un conjunto finito S de estados internos. Un conjunto finito Z de símbolos de salida. b)La tabla que define las funciones de estado siguiente y de salida de la máquina de estado finito descrito en

a/0

b/1

forma gráfica de

la máquina. A

a/0

c. Determine la cadena de salida para la cadena de entrada: aabbabaab para la máquina dada en la parte (b)

B

b/1

b/0 C a/1

Lic. Guillermo Mas Azahuanche

435

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS

Profesor: GUILLERMO MAS AZAHUANCHE

1