Question

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?

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top