Para dos lenguajes
definimos los operadores siguientes:
En efecto, veámoslo para cada operador.
Sean
y
sendos autómatas finitos que reconocen a L1 y a L2.
Intersección: Sea
el autómata producto de
y
dotado de los estados finales .
reconoce al lenguaje
y por tanto éste es regular.
Suma: Sea el autómata producto de y dotado de los estados finales . reconoce al lenguaje L1+ L2 y por tanto éste es regular.
Alternativamente, sea
la gráfica de transición que consiste de la estructura de
más la estructura de
más un estado inicial q0 con correspondientes transiciones-
y
.
Esta gráfica reconoce a L1+ L2 y por tanto éste es regular-G. Como todo regular-G es también regular, L1+ L2 es regular.
Producto: Sea
la gráfica de transición que consiste de la estructura de
más la estructura de
más un estado inicial q0 con la transición-
.
Añadamos también una transición-
de cada estado final de
al estado inicial q02 de
:
,
.
Esta gráfica reconoce a
y por tanto éste es regular-G. Así pues,
es regular.
Estrella: Sea
la gráfica de transición que consiste de la estructura de
más un estado inicial q0 con la transición-
y una transición-
de cada estado final de
a q0:
,
.
Declaremos también como final a q0. Esta gráfica reconoce a L1* y por tanto éste es regular-G. Así pues, L1* es regular.
Complemento: Sea el autómata que tiene la misma estructura de salvo en que un estado será final en si y sólo si ese estado no lo es en , es decir, F=Q-F1. Evidentemente, reconoce a L1c y por tanto éste es un lenguaje regular.