Vamos a definir a un tipo de lenguajes que denominaremos como Lenguaje Regulares (Lreg). Para lograr esto se va usar una definición recursiva.
Lenguaje Regular #
Hay dos tipos de lenguajes regulares:
- Lenguajes regulares básicos
- y los resultantes de operaciones sobre lenguajes regulares.
Lenguajes regulares básicos #
Un lenguaje \(L\) es regular si se trata de uno de los siguientes casos:
- El lenguaje \(\emptyset\) , es decir, el lenguaje vacío.
- El lenguaje \(\{ \varepsilon \}\) , es decir, el lenguaje de la cadena vacía.
- El lenguaje \(\{a\}\) donde \( a\in \Sigma \) . A este lenguaje se le conoce como el lenguaje de un símbolo del alfabeto.
Lenguajes regulares resultantes de operaciones #
Adicionalmente un lenguaje es regular si resulta de una de estas operaciones:
-
Unión
Si \(L_1\) y \(L_2\) son regulares, entonces \(L_1 \cup L_2\) es regular también.
-
Concatenación
Si \(L_1\) y \(L_2\) son regulares, entonces \( L_1 L_2\) es regular también.
-
Cerradura estrella
Si \(L\) es regular, entonces \(L^*\) es regular también.
-
Priorización por paréntesis
Si \(L\) es regular, entonces \((L)\) es regular también.
En resumen un lenguaje \(L\) es regular si corresponde con uno de los casos básicos: vacío, de la cadena vacía o lenguaje de un símbolo ; o se puede generar a través de una secuencia finita de operaciones sobre lenguajes regulares a través de las operaciones de unión, concatenación, cerradura estrella y priorización por paréntesis.
Ejemplo: número de bes pares #
¿Cómo lucen cadenas de este lenguaje?
\(\{ bb, bab, babaaaaaaa, aabaaaaabaaaabb, bbbbbbaaaaaaaabaaaaab, bababaabaabab, bbbbbbbb, \ldots \}\)¿Cómo lucen cadenas que no están en este lenguaje?
\(\{ b, bbb, ab, ba, bbbbbaaaaaaaaaaaabb, \ldots \}\)¿Cómo podríamos generar este lenguaje a través de nuestras operaciones?
Partiendo de \(\{b\}\) como regular, por ser uno de los casos básicos:
- \(\{b\}\{b\}\) es regular por concatenación, dos bes seguidas
- \(\{b\}\{a\}\{b\} \) es regular por concatenación, puede aparecer una a entre las dos bes
- \(\{b\}\{a\}^∗\{b\} \) es regular por cerradura, pueden aparecer cualquier cantidas de aes entre las dos bes
- \(\{a\}^∗\{b\}\{a\}^∗\{b\}\{a\}^∗ \) es regular por concatenación, en realidad pueden aparecer cualquier cantidad de aes antes, en medio y después de las bes
- \((\{a\}^∗\{b\}\{a\}^∗\{b\}\{a\}^∗)^∗ \) pueden aparecer cualquier cantidad de veces el patrón de dos bes con cualquier cantidad de aes antes, en medio o después.
Construcción erronea
La construcción anterior cubre la mayoría de los aspectos sin embargo deja fuera el caso en que la cadena esté conformada por puras aes; dado que una vez en el patrón de repetición que forza la cerradura estrella más externa, siempre tienen que aparecer dos bes; por lo tanto necesitamos una opción dónde aparezcan solo aes, este efecto lo podemos lograr si unimos este lenguaje con el lenguaje de puras áes resultando en la siguiente operación:
\[(\{a\}^∗\{b\}\{a\}^∗\{b\}\{a\}^∗)^∗\cup\{a\}^* \]
Algunas alternativas #
Reflexionar por qué las siguientes operaciones también generan el mismo lenguaje.
- \(\{a\}^∗(\{b\}\{a\}^∗\{b\}\{a\}^∗)^∗ \)
- \((\{a\}^∗(\{b\}\{a\}^∗\{b\})^*\{a\}^∗ \)
Respuesta
- Las repeticiones provocadas por la cerradura estrella comienzan con be, como la repetición incluye opcionalmente aes al final, a partir del primer par, podrán aparecer aes entre las segundas bes y la siguiente be; pero esto deja sin la opción de que aparezcan aes al comienzo de la cadena por lo que se concatena estas aes de forma opcional antes de la repetición.
- En este patrón, la repetición que comience con aes y que estas aparezcan entre las segundas bes y las siguiente be, sin embargo la repetición no garantiza que las cadenas puedan acabar con aes por lo que se concatenan de forma opcional al final de esta y no como parte de la repetición.