Came across this in a book, and I'm wondering why the following language is regular?

$$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$

Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a regular language because it can be expressed by a regular expression $$a*$$, and $$ \{ww^R: w \in \{a,b\}^3\} $$ is a regular language because it is finite; therefore the union of the two regular languages makes a regular language?


This is not an union of two regular languages! It's a concatenation. Note the difference,

  1. Union: $L_1 \cup L_2$
  2. Concatenation: $\{ab : a \in L_1 \wedge b \in L_2\}$.

That said, your other observations are correct, and indeed the concatenation of two regular languages is also regular itself. You can prove this by constructing two NFAs for the regular languages and connecting the accepting states of $L_1$ to the starting states of $L_2$ by an $\epsilon$-transition.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.