capitulo 9 grupos y maquinas de estado finito
Post on 09-Aug-2015
205 Views
Preview:
TRANSCRIPT
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
408
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.
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
409
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 , Sa∈∀ .
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.
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
410
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 TSf →: se le llama
ISOMORFISMO de (S,*) en (T,*´) si es:
a) INYECTIVA
b) SURYECTIVA
c) Se cumple: ( ) ( ) ( ) Sbabfafbaf ∈∀′= ,**
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
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
411
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 entonces ( - 1, -2 ) R ( 2 , 3) osea f ( -3) debe ser igual a f ( 5 )
Pero como f(-3)=10 y f (5)=18 f ( -3) ≠ f ( 5 ). Luego no existe congruencia.
TEOREMA 2: Sea R una relación de congruencia en el semigrupo (S,*).
Examínese la relación 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]).
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
412
(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.
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
413
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]
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
414
[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:
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
415
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:
•
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.
F4’ = F4
Inversos:
F1’ = F1
F2’ = F3
F3’ = F2
F5’ = F5
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.
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
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
416
El Conjunto generado por un elemento
< F4> = { F1; F4}
es el conjunto que se obtiene operando un
elemento consigo mismo como sea necesario hasta que empieza a repetirse.
< F1> = { F1}
< F2> = { F3; F1; F2}
< F3> = { F2; F1; F3}
< F5> = { F1; F5}
< 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
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
417
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
0’ = 0
1’ = 11
2’ = 10
3’ = 9
4’ = 8
5’ = 7
6’ = 6
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
418
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
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
419
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
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
420
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
( ) bcadRconQ dc
ba =⇔+,
Automorfismo.
EJERCICIOS DE APLICACIÓN 1. Sea el semigrupo ¿Probar que ( )+,Q es de
equivalencia 2. Dada la operación * definida en el conjunto { }9,7,5,3,2,1=A mediante la
tabla de doble entrada: * 1 2 3 5 7 9 1 1 2 3 5 7 9 2 2 3 1 1 4 1 3 3 2 5 7 1 7 5 5 1 3 4 1 5 7 7 5 3 3 7 9 9 9 5 1 7 1 3
Analizar si la operación * es: a) De Clausura b) Idempotente c) Conmutativa d) Si existe elemento neutro e) Si existe elemento inverso
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. GUILLERMO MAS AZAHAUNCHE
421
3.- Sea { }hgfdcbaeG ,,,,,,,= un grupo abeliano de 8 elementos en el que
todo elemento, salvo la identidad, es de orden 2, y tal que:
ahgbhfcgfchdbgdafd ====== ;;;;; . Estas relaciones son suficientes para que usted escriba la tabla del grupo. Diséñela. 4.- Dados los conjuntos: { } { }cbaBA ,,,3,2,1 =∧= se define las operaciones binarias: * y % en los conjuntos A y B respectivamente mediante:
* 1 2 3 Si f(1) = b f(2) = a f(3) = c
% a b C 1 1 2 3 a c a b 2 2 3 1 b a b c 3 3 1 2 c b c a
¿Analizar si ( ) ( ),%*, BA ∧ son isomorfos? 5.- Definimos la operación * mediante la propiedad: bababa 2−+=∗ .
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 ( ) ( )⋅+ ++ ,, ZenZ y ( ) xxfZZf 22/: =→ ++ ¿Es un homomorfismo de ( ) ( )⋅+ ++ ,, ZenZ ? 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:
=
=
=
=
=
=
312321
,123321
,231321
213321
,132321
,321321
321
321
ggg
fff
Representar la operación ∗ sobre el conjunto { }3213213 ,,,,, gggfffS = mediante una tabla de multiplicar
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 422
9.- En *RR × se define la siguiente ley *:
( ) ( ) ( ).,,, tyxzytzyx +=∗
Demostrar ( )∗× ,*RR 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.
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 423
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 Y Fw (s2) = f1 (f1 (f0(s2))) = f1 (f1 ( s1) ) = f1 ( s2) = s0.
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.
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 424
0
1
0,1
1 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.
S0
S1
S2
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 425
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: fadd o fbad = fbadadd
a, b b a
d a
d b, d
Solución: Se calcula fbad mediante la siguiente serie de transiciones:
b a d So S0 S0 S1 b a d S1 S1 S2 S1 b a d S2 S1 S2 S1. Así, fbad (s0)= s1, fbad(s1)= s1 y fbad (s2)= s1. De manera que análoga, para fadd’ a d d
S0 S0 S1 S0 a d d
S1 S2 S1 S0 a d d
S2 S2 S1 S0’ 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.
S0
S1
S2
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 426
0 0
1
1 1
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 0>∀ n
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
S0
S2
S1
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 427
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 a, b
b b
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.
S0
S1
S2
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 428
Sea ( )FISM ,,= una máquina de estado finito con conjunto de
estados: { }nSSSS ,,, 10 = , conjunto de entrada I y funciones de transición de
estados { }IxfF x ∈= / .
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 SI dada por ( ) SSI S = , para todas de en S en .
Si *
21 Ixxxw n ∈= , sea 11 xxxw ffff
nn
−= la composición de
las funciones 11
,,, xxx fffnn
− también se define Αf como SI . De esta forma, se
asigna un elemento sw Sdef con cada elemento de w de *I . Si se piensa cada
xf como efecto de la entrada x sobre los estados de la máquina M, entonces
wf representa el efecto combinado de todas las letras de entradas sobre la
palabra w, recibidas en el orden especificado por w. Se dice que wf 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
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 429
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
- La Unidad Lógica tiene
. 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).
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
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 430
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:
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 431
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:
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 432
S F G + x + x
so s1 s2 1 0 s1 s2 s1 0 1 s2 s1 s0 1 0
Si el estado inicial es so :
a) Representar la máquina M mediante un diagrama. b) Si la cadena de entrada es: + xx + x ++ x , encontrar la cadena de salida y la
cadena de estados. 2. Dadas las siguientes máquinas de estado finito:
M F G M’ F’ G’ S 0 1 0 1 S’ 0 1 0 1
S1 S2 S3 0 1 T1 T2 T3 0 1 S2 S1 S5 1 0 T2 T1 T4 1 0 S3 S2 S5 1 1 T3 T2 T4 1 1 S4 S6 S3 0 1 T4 T2 T3 0 1 S5 S2 S3 1 1 S6 S4 S5 1 0
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 F G S a b c a b c 0 2 2 7 0 0 0 1 2 2 6 1 1 0 2 2 3 2 1 1 0
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 433
3 2 2 3 1 1 0 4 8 6 8 0 0 1 5 5 5 8 1 1 0 6 4 1 4 0 0 1 7 7 7 9 0 0 0 8 5 5 8 1 1 0 9 9 7 9 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 F G S a b c a b c 0 0 0 0 0 0 1 1 1 2 1 0 0 1 2 0 0 1 0 0 1 3 7 5 7 1 1 0 4 4 4 7 0 0 1 5 3 9 3 1 1 0 6 6 6 8 1 1 1 7 4 4 7 0 0 1 8 8 6 8 1 1 1 9 1 1 5 0 0 1
10 1 1 6 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 F G S a b a b 0 0 0 1 0 1 2 1 1 0 2 0 1 1 0 3 5 3 0 1 4 4 7 1 0 5 9 3 0 1 6 6 8 0 0 7 4 7 1 0 8 6 8 0 0 9 9 5 1 0
7. Dada la máquina de estados finitos:
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 434
M F G S a b c a b c 1 6 4 2 + * x 2 8 6 4 * x + 3 3 7 1 * x + 4 7 1 8 + * x 5 4 5 6 * x + 6 4 7 5 + * x 7 1 6 5 + * x 8 2 7 1 * x +
a) Encontrar la partición correspondiente a la relación de 2-equivalencia en el
conjunto de estados. b) Encontrar la partición correspondiente a la relación de 5-equivalencia en el
conjunto de estados. c) Hallar M la máquina mínima de M . d) Hallar una función que defina el cubrimiento de M por M . 8. a) Demostrar que la relación de cubrimiento de máquinas es reflexiva y
transitiva. b) Demostrar que la equivalencia de máquinas es una relación de equivalencia. 9. Dadas las máquinas de estados finitos M1 y M2 :
M1 F1 G1 M2 F2 G2 S1 0 1 0 1 s2 0 1 0 1 a a b 0 1 x y y 0 1 b b a 0 1 y x x 0 1
a) Demostrar que M1 y M2 son equivalentes . b) 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 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 la figura .
c) Determine la cadena de salida para la cadena de
entrada:
Bbababbabaaa. En forma recursiva
para la máquina dada en la parte (b)
11.- Si se da la tabla de una máquina de estado finito:
δ 0 δ 1
δ 2 δ 3
a / 0
a / 0
a / 1
b / 0b / 1b / 0
a / 0b / 0
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Lic. Guillermo Mas Azahuanche 435
Estado presente
Entrada 0 1
Salida 0 1
0S 5S 3S 0 1 1S 1S 4S 0 0 2S 1S 3S 0 0 3S 1S 2S 0 0 4S 5S 2S 0 1 5S 4S 1S 0 1
Sug. Use el teorema: Sea Sss ji ∈, . Entonces j
k
i SS1+
≅/ si solo si j
k
i SS ≅ para todo
Ia ∈ ; ( ) ( )asfasf j
k
i ,, ≅ . Use: 400 SSS ≅≅′ , 54 SS ≅′ , 322 SSS ≅≅′ ,
53 SS =′ . La máquina equivalente será de cuatro salidas. 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 forma gráfica de
la máquina.
c. Determine la cadena de salida para la
cadena de entrada:
aabbabaab para la máquina dada en la parte (b)
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.
A
C
B
b / 1
a / 0
b / 1
a / 1
a / 0
b / 0
UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO DE INGENIERIA DE SISTEMAS
Profesor: GUILLERMO MAS AZAHUANCHE 1
top related