Toda expresión regular se interpreta como un lenguaje:
Observación 2.2
Una expresión regular K posee la CPV si y sólo si
.
Diremos que un lenguaje
es formalmente regular si existe una expresión regular
que se interpreta como L, es decir, K es tal que
.
Ya que, vistos como conjuntos de palabras, los axiomas de las expresiones regulares, se cumplen en el conjunto
se tiene, evidentemente, la
Proposición 2.1 (Coherencia)
Si dos expresiones regulares son equivalentes entonces se interpretan como un mismo lenguaje.
El recíproco también se cumple, pero su demostración excede los límites del presente curso (véase, por ej. [21]).
Proposición 2.2 (Completitud)
Si dos expresiones regulares se interpretan como un mismo lenguaje entonces son equivalentes.
El espacio cociente
se identifica naturalmente con la clase de los lenguajes formalmente regulares.
Guillermo Morales-Luna
2000-06-27