¿Es la lengua L regular?

Question

¿Podría decirme si el idioma $L=\{a^ib^j:i+j=k, k \geq 2 \}$ ¿es regular? ¿Tengo que encontrar una expresión regular para este lenguaje? ¿O qué puedo hacer para comprobar si $L$ ¿es regular o no?

Answer 1

$L$ es casi $a^*b^*$ , excepto que $\epsilon$ , $a$ y $b$ no están en él. Los lenguajes regulares se cierran bajo la diferencia, por lo que $L$ debe ser regular.

Las expresiones regulares no tienen complemento ni diferencia, por lo que hay que enumerar las opciones que son disponible. Por suerte, todas las palabras de longitud $2$ están bien, así que sólo hay que pensar en los dos primeros caracteres. Sólo pueden ser $aa$ , $ab$ o $bb$ por lo que la expresión es $aaa^*b^*|abb^*|bbb^*$ .