Sean
y
dos lenguajes. Una sustitución es una función
que a cada símbolo de
le asocia un lenguaje en
.
Naturalmente, una sustitución f se extiende a todo
haciendo
Ahora, si
es un lenguaje, definimos
Por abuso de notación denotaremos a las funciones f** y f* como f simplemente.
Proposición 8.1
Si
es un lenguaje regular y
es una sustitución, entonces f(L) es también un lenguaje regular, siempre que
,
f(e)=Ee lo sea.
En efecto, basta ver que f(L) se representa mediante una expresión regular. Pero, como L es regular, existe una expresión regular
que lo representa. Ahora bien, para cada
,
Eei es una expresión regular. Por tanto
es una expresión regular.