Given the following statements: S1 : If L is a regular language then the…

Concept

• Closure under reversal + concatenation: if L is regular, its reversal LR is also regular (build the reverse machine by reversing every transition, making the old start state the new sole accepting state, and adding a new start state with epsilon-transitions to all the old accepting states), and the concatenation of two regular languages is always regular (chain their automata). So any language built purely by reversing and concatenating a regular L stays regular.

• Regularity needs bounded memory: a finite automaton can only remember which of finitely many states it is in. A language that forces the machine to remember an arbitrarily long prefix in full (to check it against a later suffix) cannot be recognized by any finite automaton, so it is not regular — this is the substance of the pumping lemma / Myhill–Nerode theorem.

Application

S1 : {uv | u ∈ L, v ∈ LR} is exactly L · LR (the concatenation of L with its reversal). By the closure facts above, both LR and the concatenation are regular, so S1 is TRUE.

S2 : L = {wwR | w ∈ Σ*} is the set of even-length palindromes — a string followed by its own mirror image. For any alphabet with at least two symbols this is NOT regular, because accepting a string requires matching its first half against its second half symbol-by-symbol in reverse order, and the first half can be arbitrarily long — no fixed number of states can hold on to an unbounded prefix. So S2 is FALSE.

Cross-check (pumping-lemma sketch for S2)

1. Assume {wwR} is regular with pumping length p, over Σ = {0, 1}.

2. Pick the string s = wwR with w = 0p1, so s = 0p1 1 0p (length 2p + 2).

3. The pumping lemma requires a decomposition s = xyz with |xy| ≤ p and |y| ≥ 1; since |xy| ≤ p, y sits entirely inside the leading block of 0s.

4. Pumping y (repeating it, i.e. taking xy2z) inserts extra 0s only into the first block, so the first block and last block no longer have matching lengths — the pumped string is not of the form wwR, contradicting the assumption.

5. Hence {wwR} cannot be regular over a two-symbol alphabet (over a single-symbol alphabet the language degenerates to “all even-length strings”, which happens to be regular — but that special case does not make the general statement S2 true).

Result: S1 is correct and S2 is not correct.