Why is this language not Regular - w^Rw (i.e. a word concat. with its reverse)?

Question

Consider the language L = {$w^R w$ | $w \in \{a,b\}^* $} - why is this not regular?

I'm very new to the idea of formal languages and computer science, so I've likely missed something basic. However, my thoughts on this are as follows - I recently learned two things relevant to my question: 1) that the concatenation of two regular expressions is also regular 2) That if a language is regular, the reverse of its strings is also regular.

Now, granted $w^R$ nor $w$ are not regular expressions, but since each on their own would be a regular language (given that $\{w\}$ is regular, and so through 2 so is $\{w^R\}$), each can be written as a reg expression. Concatenating these two expressions together then, as the two terms in L are concatenated together, yields a new regular expression.

If a regular expression can be generated for L, why is L not regular?

I know that you can show via e.g. the pumping lemma how L is non regular, but could you show me where I've gone wrong in my reasoning above (probably many places), as my goal is to properly understand the concepts?

Many thanks, indeed! Really appreciate it.

Answer 1

Hint. Suppose that $L$ is regular. Since regular languages are closed under intersection, then $L \cap a^*bba^* = \{a^nbba^n \mid n \geqslant 0 \}$ should be regular.

Answer 2

The problem is that what you call $w$ and $w^R$ are not independent. Probably your expression for $w$ is an expression that generates all words; similarly the expression for $w^R$ generates all the reverses of words (which. by the way, is the same set).

To put together your language you now do not need catenation, but the operation "catenate every string with its reverse, but not with others" - this is not regular, and the expression you propose is not a regular expression.

A tiny example: words $\{ab, aa\}$; reverses $\{ba,aa\}$. The pure catenation contains $abaa$ and $aaba$, which are not of the required form.

Answer 3

Can you draw DFA for $w^R$, if DFA of $w$ exists?

Yes, you can draw this DFA too, by reversing existing DFA.

Can you draw DFA for concatenation of two strings of same language?

Yes, you can draw this DFA too.

Can you draw DFA for language $w^Rw$, if it is not finite language, means contains Kleene star(*)?

No, not at all. Because you need comparison $w$ with $w^R$, since language is not finite (i.e, $w \in (a+b)^*$) and you can not store more than one bit in a DFA state. Each DFA state can store only 1 bit data (either 0 or 1).

Infinite comparisons is not allowed in DFA, but infinite condition is allowed.

$L = \{w^Rw \mid w \in \{a,b\}^*\}$ has infinite number of comparisons not condition.