Determining whether a given language is regular, and finding a regular expression

Question

I know there are a lot of questions similar to this one, Proving a language is regular is just one example. However, I have not managed to find an answer that really answers my question. I'm currently studying for an exam in automata theory, and hence trying to understand how it all works. So, given the following language, how do I determine whether it is regular or not?

$L_1 = \{uvu^{rev} : u, v \in \{a, b\}^*\ and\ \lvert u \rvert = 2\}$

I'm not quite sure how I should be approaching this issue, and how $u^{rev}$ and $\lvert u\rvert$ affect the regularity of a language. My get instinct would be that a machine could handle the reverse if we know its length, but not otherwise, but I can't tell exactly why that would be true. Or perhaps it is that the middle part must be known and we must know the length of $v$ instead?

Furthermore, the problem continues with a second language

$L_1 = \{uvu^{rev} : u, v \in \{a, b\}^*\ and\ \lvert v \rvert = 2\}$

So the exact same language, but we now know the length of $v$.

It's clear to me that one of the languages is regular and the other not, but I am struggling to find a good explanation as to why that is, and how to properly argue for either.

It should also be noted that the question specifies that

If the expression is regular, a regular expression and/or closure properties should be used to prove this. Otherwise, a proof using the pumping lemma should be given.

I'm not quite sure how to approach this, so any help would be much appreciated, and preferably not just a solution but an explanation for it too!

Answer 1

I’ll get you started. It makes a very great difference whether we restrict the length of $u$ or the length of $v$. Let’s look first at restricting the length of $u$.

Since the alphabet is $\{a,b\}$, when we require that $|u|=2$, we’re actually saying that $u$ must be one of the words $aa,ab,ba$, and $bb$. This means that words of $L_1$ have one of the following four forms, where $v\in\{a,b\}^*$: $aavaa,abvba,bavab$, and $bbvbb$. Can you write regular expressions for each of these forms and then combine them to get a regular expression for $L_1$?

When we require instead that $|v|=2$, we’re saying that $L_2$ consists of the words of the forms $uaau^{rev},uabu^{rev},ubau^{rev}$, and $ubbu^{rev}$, where $u$ can be any word in $\{a,b\}^*$. Getting a regular expression for one of these forms is no easier than getting one for the set of words of the form $uu^{rev}$, and that language is not regular. I’ll get you started on a pumping lemma proof that $L=\big\{uu^{rev}:u\in\{a,b\}^*\big\}$ is not regular; see if you can modify it to show that $L_2$ is not regular.

I’ll assume that you’ve seen the pumping lemma used. Suppose that $L$ is regular, and let $p$ be the pumping length. Let $w=a^pbba^p$; clearly $w\in L$. The pumping lemma says that $w$ can be decomposed as $w=xyz$ in such a way that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for each $k\ge 0$. Note that these conditions imply that $y$ is a non-empty substring of the first string of $a$s in $w$; what happens when you pump (i.e., when you change $k$ from $1$ to some other natural number)?