Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

https://produccioncientificaluz.org/index.php/divulgaciones/

DOI: https://doi.org/10.5281/zenodo.7487423

(CC BY-NC-SA 4.0)

Autor(es)

e-ISSN 2731-2437

p-ISSN 1315-2068

Estructura algebraica de los aut´omatas ﬁnitos y

lenguajes

Algebraic structure of ﬁnite automata and languages

Fernando Ortiz (fernandojavier12037@gmail.com)

ORCID: https://orcid.org/0000-0002-1048-3478

Instituto de Postgrado

Universidad T´ecnica de Manab´ı.

Av.Urbina y Che Guevara, 130103, Ecuador.

Luz Sol´e (luzsole@gmail.com)

ORCID: https://orcid.org/0000-0001-6783-1819

Departamento de Matem´aticas, Facultad de Ciencias

Universidad de los ´

Andes

M´erida 5101, Rep´ublica Bolivariana de Venezuela

Resumen

Estableceremos a los aut´omatas ﬁnitos mediante un enfoque algebraico, donde todos los

argumentos y pruebas son constructivas; y donde el concepto fundamental para dicho enfo-

que esta centrado en la multiplicidad.

Palabras y frases clave: Aut´omatas ﬁnitos, comportamiento din´amico, multiplicidad.

Abstract

We will present ﬁnite automata through an algebraic approach, where all the arguments

and proofs are constructive; and where the fundamental concept for this approach is centered

on multiplicity.

Key words and phrases: Finite automata, dynamic behavior, multiplicity.

1 Introducci´on

Presentamos una estructura algebraica la cual ser´a aplicada a los aut´omatas ﬁnitos [1, 4, 5, 2, 3],

donde la noci´on b´asica que nos permitir´a tal extensi´on es la multiplicidad. Para ser m´as precisos,

sea A= (Q, Σ, E, I, T) un aut´omata, y sea |A| su correspondiente comportamiento din´amico,

cada camino c:i→t,i∈I, t ∈Tcon etiqueta |c|=sdetermina que s∈ A; m´as a´un, si nes

el n´umero de tales caminos, entonces podemos establecer una funci´on Σ∗→Nla cual especiﬁca

la multiplicidad de los elementos s∈Σ∗. En este caso diremos que s∈ |A| con multiplicidad n.

Tambi´en, con abuso de lenguaje escribiremos la funci´on de multiplicidad como |A| : Σ∗→N,

Recibido 29/06/2021. Revisado 17/09/2021. Aceptado 23/11/2021.

MSC (2010): Primary 37N35; Secondary 93C65.

Autor de correspondencia: Luz Sol´e

Estructura algebraica de los aut´omatas ﬁnitos y lenguajes 11

|A|(s) = n, y la llamaremos el comportamiento de A. Note que de acuerdo a lo establecido,

|A|(s) = 0 signiﬁca que s /∈ |A|. As´ı, identiﬁcamos a |A|, el cual es un subconjunto ordinario de

Σ∗, con la aplicaci´on |A| : Σ∗→N. Por otro lado, sin consideraciones de multiplicidad cualquier

subconjunto Ade Σ∗puede ser visto como una funci´on A: Σ∗→β, donde β={0,1}. La

identiﬁcaci´on es dada por la relaci´on: s∈A⇐⇒ A(s) = 1. Finalmente, nos confrontamos con

dos clases de “Subconjuntos” de Σ∗(N-subconjuntos y β-subconjuntos) las cuales corresponden,

uniﬁcadamente, al concepto de un semianillo K.

2 Nociones preliminares

Nosotros asumiremos que son conocidos los conceptos y resultados b´asicos de las teor´ıas de

aut´omatas y lenguajes. Por su parte,

Deﬁnici´on 2.1. Un semianillo Kes un conjunto dotado de dos operaciones: suma(+) y mul-

tiplicaci´on ·; tal que (K, +) es un monoide conmutativo con elemento neutro 0 y (K, ·) es un

monoide con elemento identidad 1. Adem´as, para todo x, y, z ∈Kse tiene que

x(y+z) = xy +xz (y+z)x=yx +zx

x0=0=0x.

Un semianillo Kes llamado conmutativo si (K, ·) es conmutativo. Claramente, todo anillo

con unidad es un semianillo. Ejemplos de algunos semianillos conmutativos.

Ejemplo 2.1. Sea β={0,1}es un semianillo, donde la suma esta dada por

1 + 1 = 1 0 + 0 = 0

0 + 1 = 1 1 + 0 = 1.

Note que 0es el elemento neutro. La multiplicaci´on est´a dada por

1·1 = 1 0 ·0=0

0·1 = 0 1 ·0=0.

donde 1es el elemento identidad.

Ejemplo 2.2. El conjunto Nes el semianillo de todos los enteros n≥0, con la suma y la

multiplicaci´on usual.

Ejemplo 2.3. El conjunto Nes el semianillo Njunto con un elemento adicional ∞, donde la

suma y la multiplicaci´on son extendidas por

n+∞=∞ ∞ +n=∞ ∞ +∞=∞

n· ∞ =∞, n 6= 0 ∞ · n=∞;n6= 0 ∞·∞=∞

∞ · 0=0=0· ∞.

Ejemplo 2.4. El conjunto R+es el semianillo de todos los n´umeros reales x≥0, con la suma

y la multiplicaci´on usual.

Ejemplo 2.5. El conjunto R+es el semianillo de los n´umeros R+junto con ∞, donde las

operaciones se extienden exactamente como en el caso de NaN.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

12 Fernando Ortiz - Luz Sol´e

Sea {xi}i∈Iuna familia arbitraria de elementos de un semianillo K, donde Ies un conjunto

cualquiera de ´ındices; es decir, una aplicaci´on ϕ:I−→ K, tal que ϕ(i) = xi,i∈I. Si Ies ﬁnito,

la suma

i∈I

xi∈K(2.1)

Esta suma tiene las siguientes propiedades:

Si I={i},entonces X

i∈I

xi=xi(2.2)

Si I=[

j∈J

Ijes una partici´on de Iyz∈K, entonces

i∈I

xi=X

j∈J X

i∈IJ

xi!(2.3)

z X

i∈I

xi!=X

i∈I

zxi(2.4)

i∈I

xi!z=X

i∈I

xiz(2.5)

Si I=∅,entonces X

i∈I

xi= 0 (2.6)

Ahora, considerando a (2.1) en lugar de la suma x+yy tomando (2.2)-(2.6) y (K, ·) el monoide

dado como axiomas, entonces podemos deﬁnir

x1+x2=X

i∈I

xi,con I={1,2}y 0 = X

i∈I

xi,si I=∅.

En consecuencia, bajo esta axiom´atica, tenemos una forma equivalente para deﬁnir un semi-

anillo. En efecto, la conmutatividad y asociatividad se obtienen del hecho siguiente: si ϕ:J→I

es una biyecci´on, entonces

i∈I

xi=X

j∈J

xϕ(j).

Por otro lado, la distributividad a izquierda y derecha se obtienen de (2.4) y (2.5). Enfatizamos

que (2.1) es deﬁnida si Ies ﬁnito. Ahora, si para cualquier conjunto de ´ındices I, (2.1) est´a bien

deﬁnida como elemento de K, entonces bajo nuestra nueva deﬁnici´on de semianillo, se obtiene la

noci´on de semianillo completo. Finalmente, todo semianillo completo es un semianillo.

Los anillos N,R+, β son completos ya que la suma puede extenderse de manera natural para

deﬁnir (2.1), para cualquier conjunto de ´ındices I, esto es, usando el orden usual en N,R+, β

puede deﬁnirse (2.1) como la menor de las cotas superiores de los elementos X

i∈J

xi, donde J

recorre todos los subconjuntos ﬁnitos de I.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

Estructura algebraica de los aut´omatas ﬁnitos y lenguajes 13

Deﬁnici´on 2.2. Dados dos semianillos KyK0, un homomorﬁsmo ϕ:K−→ K0es una funci´on

que satisface:

ϕ(x1+x2) = ϕ(x1) + ϕ(x2),

ϕ(0) = 00(2.7)

ϕ(x1·x2) = ϕ(x1)·ϕ(x2),

ϕ(1) = 10.(2.8)

Notemos que si Ies ﬁnito, entonces

ϕ X

i∈I

xi!=X

i∈I

ϕ(xi) (2.9)

Observaci´on 2.1.Si KyK0son completos entonces (2.7) es reemplazado por (2.9) para Iarbi-

trario.

Deﬁnici´on 2.3. Un semianillo Kser´a llamado positivo si satisface:

1. 0 6= 1.

2. si x+y= 0, entonces x=y= 0.

3. si xy = 0, entonces x= 0 ´o y= 0.

Sea Kun semianillo y consid´erese T:K→βdada por:

T(x) = (1,six= 0

0,six6= 0

Entonces, Tes un homomorﬁsmo si, y s´olo si, Kes positivo.

En lo que sigue asumiremos que Kes un semianillo no trivial (0 6= 1) y conmutativo.

Deﬁnici´on 2.4. Sea Xun conjunto. Un subconjunto Ade Xes una funci´on A:X−→ K. Para

cada x∈X, el elemento A(x) ser´a llamado la multiplicidad con la cual xpertenece a ˙

A. Si los

valores que toma Ason 0 y 1, diremos que el subconjunto Ade Xes no ambiguo.

Si K=β, entonces todos los subconjuntos de Xson no ambiguos. Los subconjuntos Ade X

no ambiguos pueden ser identiﬁcados con el subconjunto {x:A(x)=1}de X(recordemos que

hemos supuesto 0 6= 1).

Ejemplo 2.6. Sea X, ∅yx, para cada x∈X, dados por:

1. X(x)=1, para todo x∈X;∅(x) = 0, para todo x∈X;

2. x(y) = (1,si x=y

0,en otro caso,

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

14 Fernando Ortiz - Luz Sol´e

son subconjuntos no ambiguos. Los subconjuntos no ambiguos xser´an llamados “simples”. Si

Aes un subconjunto no ambiguo de X, las notaci´ones x∈AyA(x) = 1 son sin´onimos.

Finalmente, si Aes un subconjunto de Xyϕ:K→K0es un homomorﬁsmo de semianillos,

entonces la composici´on

−−−→ Kϕ

−−→ K0

es un subconjunto ϕ(A) de X.

La primera operaci´on que consideraremos es la suma o uni´on, denotada por P´o ∪respecti-

vamente. Para cada familia indizada {Ai}i∈Ide subconjuntos de X, deﬁnimos

[

i∈I

Ai!(x) = X

i∈I

Ai!(x) = X

i∈I

Ai(x) (2.10)

Esta deﬁnici´on no requiere comentario si Kes completo. En otro caso, se asumir´a que la

familia {Ai}i∈Ies localmente ﬁnita; es decir, para cada x∈Xse tiene que Ai(x) = 0 excepto

para un n´umero ﬁnito de elementos i∈I.

Si I={1,· · · , n}, se usar´a la notaci´on

A1∪A2∪ · · · ∪ An´o A1+A2+· · · +An

en lugar de [

i∈I

Ai´o X

i∈I

Ai, respectivamente.

La segunda operaci´on es la multiplicaci´on de k∈Kpor un subconjunto A. El resultado es

un subconjunto kA deﬁnido por

(kA)(x) = kA(x) (2.11)

A partir de las deﬁniciones previas, se tienen las siguientes propiedades:

1A=A, 0A=∅,(k1k2)A=k1(k2A), X

i∈I

ki!A=X

i∈I

kiA, k X

i∈I

Ai!=X

i∈I

kAi.

La intersecci´on A∩Bde dos subconjuntos es deﬁnida por:

(A∩B)(x) = A(x)B(x).

Tambi´en, deﬁnimos la intersecci´on cuando Bes un subconjunto y Aes un subconjunto no

ambiguo con respecto a β. En este caso se tiene que:

(A∩B)(x) = (B(x),si x∈A

0,si x /∈A

Ahora, para cada subconjunto Ade Xse tiene que:

A=X

x∈X

A(x)x.

Esta suma est´a bien deﬁnida. En efecto. La familia {A(x)x}x∈Xes localmente ﬁnita:

(A(x)x)(y) = (A(x),si x=y

0,en otro caso

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

Estructura algebraica de los aut´omatas ﬁnitos y lenguajes 15

x∈X

A(x)xes llamada la expansi´on de A(en t´erminos de simples). Esta es una forma ´util

de manipular los subconjuntos. En efecto,

Ejemplo 2.7.

kA =X

x∈X

kA(x)x A ∩B=X

x∈X

A(x)B(x)x

Sea Aun subconjunto de Xy sea X0un subconjunto no ambiguo con respecto a βde X. Si

A(x) = 0 para todo x∈X\X0, entonces Aes un subconjunto de X0. En este caso, escribimos

A⊂X0. Finalmente, obtenemos que:

A⊂X0⇔A∩X0=A.

Nuestro inter´es ahora es estudiar el producto entre dos subconjuntos de S, donde (S, ·) es un

semigrupo.

Deﬁnici´on 2.5. Sean (S, ·) un semigrupo y A,Bsubconjuntos de S, con Kcompleto. El sub-

conjunto AB de Ses dado por:

(AB)(z) = X

xy=z

A(x)B(y) (2.12)

Observaci´on 2.2.1. La f´ormula para el producto AB, dada en la ecuaci´on (2.12), es incluida

para garantizar la bilinealidad del producto.

2. Sea z∈S, pueden existir inﬁnitos pares (x, y) tales que xy =z. Por esta raz´on es necesario

que Ksea completo. Sin embargo, si S= Σ+es el semigrupo libre con base Σ (no necesa-

riamente ﬁnito), entonces el n´umero de factorizaciones xy =zes exactamente |z| − 1. En

consecuencia, la suma en (2.12) es ﬁnita y Kpor lo tanto no tiene porque ser completo. El

mismo argumento se aplica si S= Σ∗.

As´ı, AB es bilineal. En efecto. Sean {Ai}i∈Iy{Bj}j∈Jfamilias de subconjuntos de S, entonces

i∈I

Ai!B=X

i∈I

AiB A 

X

j∈J

Bj

=X

j∈J

ABj

(kA)B=k(AB) = A(kB).

Adem´as, AB es asociativa. Finalmente, si Mes un monoide, entonces KMes un semianillo (no

necesariamente conmutativo) con identidad el elemento simple θ, donde θes la identidad de M.

Sean PyQconjuntos ﬁnitos. Un subconjunto de P×Qes una matriz donde las ﬁlas y las columnas

son indizadas con elementos de PyQrespectivamente, con entradas en K. Si A∈KP×Q, en

lugar de escribir A(p, q), escribiremos Apq y la matriz la identiﬁcaremos como A= [Apq]. La suma

de matrices es deﬁnida usando la suma de subconjuntos. Esto es, si B∈KP×Q, entonces

(A+B)pq =Apq +Bpq

Una nueva operaci´on es la multiplicaci´on de matrices. Sean A∈KP×QyB∈KQ×R, el producto

AB ∈KP×Qest´a deﬁnido por:

(A·B)pr =X

q∈Q

ApqBqr .

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

16 Fernando Ortiz - Luz Sol´e

Las propiedades usuales de la multiplicaci´on son f´acilmente establecidas. Si P=Q, entonces

KP×Pes un semianillo con unidad 1P, donde

(1P)qq0=(1,si q=q0

0,si q6=q0

Si A∈KP×QyPes unitario, entonces Aes llamado vector ﬁla. Si Qes unitario, entonces A

es llamado vector columna.

3 Aut´omatas ﬁnitos sobre un semianillo conmutativo

Deﬁnici´on 3.1. Sean Σ un alfabeto ﬁnito y Kun semianillo conmutativo. Un K-aut´omata A

es un quintuple

A= (Q, Σ, E, I, T ),

donde Qes un conjunto ﬁnito, IyTson subconjuntos de Q, y Ees un subconjunto de Q×Σ×Q.

Sea A= (Q, Σ, E, I, T ) un K-aut´omata. Si E(p, α, q) = k6= 0, entonces diremos que existe

un arco de paqque denotaremos pkα

−−−→ qcon etiqueta kα. En este caso, tambi´en diremos que

pkα

−−−→ qest´a en A.

Como en el caso de los aut´omatas, se consideran los caminos o trayectorias c:p→q. As´ı, si

ces un camino

pk1α1

−−−−−→ q1

k2α2

−−−−−→ · · · qn−1

knαn

−−−−−→ q,

entonces su etiqueta es |c|=ks, con K=k1· · · knys=α1· · · αn, y su longitud es kck=n=|s|.

Deﬁnici´on 3.2. Sea A= (Q, Σ, E, I, T ) un K-aut´omata. El comportamiento de Aes el subcon-

junto de Σ∗, denotado |A|, dado por:

|A| =X

p,q∈QX

I(p)|c|T(q).(3.1)

con crecorriendo todos los caminos c:p→q; es decir,

|A|(s) = X

p,q∈QX

k∈C

I(p)kT (q),

donde C={k∈K:∃c:p→q, |c|=ks}.

Observaci´on 3.1.1. Para cada s∈Σ∗, existe solo un n´umero ﬁnito de caminos con etiquetas

ks,k∈K. Luego, la suma (3.1) es localmente ﬁnita y en consecuencia |A| est´a bien deﬁnido

sin asumir que Ksea completo.

2. Los ´unicos caminos con longitud 0 son los triviales, es decir, los caminos

c:p−→ p, con etiqueta |c|= 1θ.

En consecuencia,

|A|(θ) = 

X

p,q∈QX

l(p)|c|T(q)

(θ) = X

p∈Q

I(p)T(p) = IT

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

Estructura algebraica de los aut´omatas ﬁnitos y lenguajes 17

donde IT es producto del vector ﬁla I= (I(p1),· · · , I(pn)) por el vector columna 





T(p1)

T(pn)





.

El subconjunto Ede Q×Σ×Qes una funci´on

E:Q×Σ×Q→K.

Denotaremos E(p, α, q) = Epq(α).As´ı, para todo p, q ∈Q, Epq es un subconjunto de Σ. De esta

manera, Epuede ser vista como una matriz

E:Q×Q→KΣ,

llamada matriz de transici´on. Cada subconjunto de Σ puede extenderse a un subconjunto de Σ∗

poniendo, para p, q ∈Q,

Epq :Σ∗−→ K,

Epq(s) = (Epq(s),si s∈Σ

0,si s /∈Σ.

De manera que, Epuede ser vista como un subconjunto de Q×Q; es decir, como una matriz

Q×Qcon entradas en KΣ∗. Por lo tanto, como KΣ∗es un semianillo, podemos utilizar las

operaciones correspondientes. Ahora bien, para cada n∈N, deﬁnimos las matrices

En:Q×Q−→ KΣ∗,

E0=1Q, E1=E, . . . , En=EEn−1, n ≥2,donde

pq =X

r∈Q

EpqEn−1

rq ,con p, q ∈Q.

Claramente, si s∈Σ∗y|s| 6=n, entonces En

pq(s) = 0, con p, q ∈Q. Luego, {En

pq}n∈Nes localmente

ﬁnita. As´ı, podemos deﬁnir

E∗

pq =

∞

n=0

y en consecuencia, obtenemos la matriz

E∗:Q×Q−→ KΣ∗

E∗=1Q+E+E2+· · · +En+· · ·

llamada matriz de transici´on extendida. Para cada s∈Σ∗, consideremos la matriz

E∗(s)=[E∗

pq(s)] ∈KQ×Q.

Si s=α1· · · αn, entonces

E∗(s) = En(s) = E(α1)· · · E(αn) = E∗(α1)· · · E∗(αn).

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

18 Fernando Ortiz - Luz Sol´e

4 Resultados te´oricos

Teorema 4.1. Para cualesquiera p, q ∈Q, el subconjunto E∗

pq es la suma de todas las etiquetas

de caminos c:p−→ qen A.

Demostraci´on. Sean p, q ∈Q, como E∗

pq =

∞

pq=1

pq es suﬁciente comprobar que En

pq es la suma

de todas las etiquetas de los caminos de longitud n.

Si n= 0, entonces

pq =(θ, si p=q

φ, si p6=q

donde θes la identidad de KΣ∗.

Si n= 1, entonces

pq =X

r∈Q

Epr(1Q)rp =X

r∈Q

EprE0

rq .

Supongamos que el resultado es cierto para n−1, n≥2; es decir,

En−1

pq =X

r1,··· ,rn−1∈Q

Epr1Er1r2· · · Ern−1q=X

r∈Q

EprEn−2

rq .

Entonces,

pq =X

r∈Q

EprEn−1

rq =X

r1∈Q

Epr1

X

r2,··· ,rn∈Q

Er1r2Er1r3· · · Ernq



r1,··· ,rn∈Q

Epr1Er1r2· · · Ernq=X

r∈Q

EprEn−2

rq .

As´ı, En

pq es la suma de todas las etiquetas de los caminos con longitud n. Luego, E∗

pq es la

suma de todas las etiquetas de los caminos c:p→qen A.

Corolario 4.1. El comportamiento de Aes |A| =IE∗T, con Ivisto como un vector ﬁla y T

como un vector columna.

Demostraci´on.

|A| =X

p,q∈QX

I(p)|c|T(q) = X

p,q∈Q

l(p)E∗

pqT(q) = IE∗T.

Deﬁnici´on 4.1. Sean Kun semianillo conmutativo y Σ un alfabeto ﬁnito. Un subconjunto A

de Σ∗es llamado regular si existe un K-aut´omata Atal que |A| =A.

Cuando consideremos dos K-aut´omatas A= (QA,Σ, EA, IA, TA) y B= (QB,Σ, EB, IB, TB),

asumiremos que QA∩QB=∅.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

Estructura algebraica de los aut´omatas ﬁnitos y lenguajes 19

Deﬁnici´on 4.2. Sean A,B, dos K-aut´omatas, el K-aut´omata uni´on de AyBes dado por

A∪B= (QA∪B,Σ, EA∪B, IA∪B, TA∪B)

donde, QA∪B=QA∪QB,

IA∪B(p) = (IA(p),si p∈QA

IB(p),si p∈QB

TA∪B(p) = (TA(p),si p∈QA

TB(p),si p∈QB

EA∪B(p, α, q) = 









EA(p, α, q),si p, q ∈QA

EB(p, α, q),si p, q ∈QB

0,en otro casob

Observaci´on 4.1.Un camino en A∪B es un camino en Ao es un camino en B.

Proposici´on 4.1. La uni´on de dos subconjuntos regulares de Σ∗es un subconjunto regular de

Σ∗.

Demostraci´on. Sean AyBdos subconjuntos regulares de Σ∗, y A,Bdos K-aut´omatas tales que

|A| =Ay|B| =B. Consideremos el K-aut´omata A∪B, entonces, para todo s∈Σ∗,

|A ∪ B|(s) = 

X

p,q∈QA∪BX

IA∪B(p)|c|TA∪B(q)

(s) = X

p,q∈QA∪QBX

IA∪B(p)kTA∪B(q),

donde k∈Kes tal que existe un camino c:p−→ qen A∪B con |c|=ks,

|A ∪ B|(s) = X

p,q∈QAX

IA(p)kTA(q) + X

p,q∈QBX

IB(p)kTB(q)

=|A|(s) + |B|(s) = A(s) + B(s) = (A∪B)(s).

As´ı, |A ∪ B| =A∪B.

Deﬁnici´on 4.3. Sean A,Bdos K-aut´omatas. El K-aut´omata producto (o intersecci´on) de Ay

Bes dado por A×B= (QA×B,Σ, EA×B, IA×B, TA×B), donde

QA×B=QA×QB, IA×B(p, q) = IA(p)IB(q),

TA×B(p, q) = TA(p)TB(q), EA×B((p, q), α, (p0, q0)) = EA(p, α, p0)EB(q, α, q0).

Observaci´on 4.2.Un camino c: (p, q)−→ (p0, q0) en A×B, con etiqueta |c|=ks, puede ser visto

como un par c= (c0, c00),donde c0:p−→ pes un camino en A, con |c0|=k1syc00 :q−→ q0es

un camino en B, con |c00|=k2s, con k1k2=k.

Proposici´on 4.2. La intersecci´on de dos subconjuntos regulares de Σ∗es un subconjunto regular

de Σ∗.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

20 Fernando Ortiz - Luz Sol´e

Demostraci´on. Sean AyBdos subconjuntos regulares de Σ∗yA,Bdos K-aut´omatas tales que

|A| =Ay|B| =B. Consideremos el K-aut´omata A×B. Entonces, para todo s∈Σ∗,

|A × B|(s) = 

X

(p,q),(p0,q0)∈QA×QBX

IA×B(p, q)|c|TA×B(p0, q0)

(s)

=

X

p,p0∈QA;q,q0∈QBX

(c0,c00 )

IA(p)IB(q)|(c0, c00)|TA(p0)TB(q0)

(s)

donde c0:p−→ p0es un camino enAycn:q−→ q0es un camino en B,

p,p0∈QA;q,q0∈QBX

k1,k2

IA(p)k1TA(p0)IB(q)k2TB(q0)

p,p0∈QA;q,q0∈QBX

k1,k2

IA(p)k1TA(p0)IB(q)k2TB(q0)

donde |c0|=k1s,|c00|=k2syk1k2=kcon ks =|c|,

p,p0∈QAX

IA(p)k1TA(p0)X

q,q0∈QBX

IB(q)k2TB(q0)

=

X

p,p0∈QAX

IA(p)|c0|TA(p0)

(s)

X

q,q0∈QBX

c00

IB(q)|c00|TB(q0)

(s)

=|A|(s)|B|(s)=(|A| ∩ |B|)(s)=(A∩B)(s)

Deﬁnici´on 4.4. Un K-aut´omata A= (Q, Σ, E, I, T ) es llamado normalizado si I={i}y

T={t}(o simplemente I=iyT=t) son dos subconjuntos simples distintos, y no existen arcos

qkα

−−−→ i,tkα

−−−→ q, con k6= 0, es decir, E(q, α, i) = E(t, α, q) = 0 para todo q∈Qyα∈Σ.

Proposici´on 4.3. Para cada K-aut´omata Aexiste un K-aut´omata normalizado A0tal que

|A0|=|A| ∩ Σ∗.

Demostraci´on. Sea A= (Q, Σ, E, I, T ) un K-aut´omata y consideremos Q0=Q∪i∪t, donde iy

tson dos nuevos estados distintos. Deﬁnimos la nueva matriz E0como sigue:

pq =Epq, E0

iq =X

p∈Q

lpEpq, E0

pt =X

q∈Q

EpqTq, E0

it =X

p,q∈Q

lpEpqTq, E0

pi =Eti =Etq =∅,

donde lp=I(p) y T(q) = Tq. Un c´alculo simple determina que E0∗

it =IE+T, donde E+=

E+E2+· · · +En+· · · =EE∗. El K-aut´omata A0= (Q0,Σ, E0, i, t) es normalizado, y usando

el corolario 4.1 se tiene

|A0|=E0∗

it =IE+T=IE∗T∩Σ+=|A| ∩ Σ+

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

Estructura algebraica de los aut´omatas ﬁnitos y lenguajes 21

Proposici´on 4.4. Sea Aun subconjunto regular de Σ∗y sea k∈K, entonces kA es un subcon-

junto regular de Σ∗.

Demostraci´on. Sea Aun K-aut´omata tal que |A| =A, y sea k∈K. Consideremos el K-aut´omata

kA= (Q, Σ, E, kI, T ), donde (kI)q=kIq(Ivisto como un vector ﬁla), entonces

|kA| =X

p,q∈Q

klpE∗

pqTq=kX

p,q∈Q

lpE∗

pqTq=k|A| =kA.

Proposici´on 4.5. Un subconjunto Ade Σ∗es regular si, y s´olo si, el subconjunto A0=A∩Σ+

tambi´en lo es.

Demostraci´on. Sea Aun K-aut´omata tal que |A| =A. Entonces, existe un K-aut´omata (normali-

zado) A0tal que |A0|=|A|∩Σ+=A∩Σ+=A0. Reciprocamente, supongamos que A∩Σ+=A0es

un subconjunto regular de Σ∗. Como A0(θ) = 0 (ya que Σ+(θ) = 0), podemos escribir A=kθ+A0

donde k=A(θ). Ahora, como θes un subconjunto regular de Σ∗, entonces por las proposiciones

4.1 y 4.4 se tiene que Aes regular.

Proposici´on 4.6. Si AyBson subconjuntos regulares de Σ∗, entonces AB tambi´en lo es.

Demostraci´on. Sea A=kθ +A0,B=lθ +B0, con A0=A∩Σ+,B0=B∩Σ+,k=A(θ) y

l=B(θ). Entonces, AB =klθ +kB0+lA0+A0B0. Basta probar que A0B0es regular. Para esto,

sean A= (Q1,Σ, E1, i1, t1) y B= (Q2,Σ, E2, i2, t2) dos K-aut´omatas normalizados que reconocen

aA0yB0respectivamente. Consideremos el K-aut´omata normalizado C= (Q, Σ, E, i1, t2), donde

Qes la uni´on disjunta de Q1yQ2, salvo la consideraci´on t1=i2. Luego un arco en Ces un arco

en Ao es un arco en B. As´ı, claramente

|C| =E∗

i1t2=E∗

1i1t1E∗

2i2t2=|A||B| =A0B0.

Teorema 4.2. Un subconjunto Ade Σ+es regular si, y s´olo si, existe un entero n > 1yEuna

matriz n×ncuyas entradas son subconjuntos de Σtal que A=E+

1n.

Demostraci´on. Supongamos que Aes un subconjunto regular de Σ+, y sea A= (Q, Σ, E, i, t)

un K-aut´omata normalizado que reconoce a A. Sin perdida de generalidad supongamos que

Q={1,· · · , n},con i= 1 y t=n. Como i6=tse tiene que n > 1. Ahora, por el corolario 4.1

se tiene que |A| =E∗

1n=E+

1n=A. Reciprocamente, si A=E+

1n, donde Ees una matriz n×n

de subconjuntos de Σ y n > 1, entonces poniendo Q={1,· · · , n},I= 1 y T=n, obtenemos un

K-aut´omata A= (Q, Σ, E, l, n) que como antes |A| =E+

1n=A.

Corolario 4.2. Si Ees una matriz n×nde subconjuntos de Σ, entonces para cualesquiera

1≤i, j ≤n, los subconjuntos E∗

ij yE+

ij son regulares.

Demostraci´on. Inmediato desde el teorema 4.2

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22

22 Fernando Ortiz - Luz Sol´e

5 Conclusi´on

Si K=NyA= (Q, Σ, E, I, T ) es un K-aut´omata, entonces Qes un conjunto ﬁnito, IyTson

dos subconjuntos de Q, y Ees un subconjunto de Q×Σ×Q; luego, si I, T yEson no ambiguos

se sigue que Aes un aut´omata ﬁnito en el sentido convencional. As´ı, los K-aut´omatas, con Kun

semianillo conmutativo, extienden naturalmente a los aut´omatas. Mas a´un si Aes un subconjunto

regular de Σ∗con respecto a N, existe un N-aut´omata no ambiguo Atal que |A| =A.

Referencias

[1] Branicky, M., (1995), Studies in hibrid systems: Modeling, analysis and control. PhD thesis,

Massachusetts inst technol, Cambridge, Dept. Elec. Fng. And computer Sci.

[2] Eilemberg, S., (1974), Automata, languages and machines, Vol. A. Academic Press, New

York.

[3] Glasserman, P. and Yao, D., (1991), Algebraic structure of some Discrete Event Sistems with

Application. J. On DEDS, Vol. 1.

[4] Hopcroft, J. E. and Ullman, J. D., (1979), Introduction to Automata theory, languages, and

computation, Addison Wesley USA.

[5] Mata, G., Ruiz, B., Camacho, C., M´endez, A., Mu˜noz, S., and Zambrano, H., (2018), A

planning algorithm in a class of discrete event system. DYNA. 85(206),283-293.

Divulgaciones Matem´aticas Vol. 22, No. 2 (2021), pp. 10–22