# Prove A² is regular [duplicate]

This question already has an answer here:

Suppose that $A$ is a regular language. How can I show that $A^2 = A \cdot A$ is a regular language? Is there a construction?

## marked as duplicate by Juho, David Richerby, D.W.♦, Luke Mathieson, Nicholas MancusoMar 19 '15 at 4:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your (home-)work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? – Raphael Mar 17 '15 at 6:21
• Hint: check the proof for the fact that finite automata and regular expressions define the same set of languages. – Raphael Mar 17 '15 at 6:22

## 1 Answer

This holds more generally:

Theorem. If $X$ and $Y$ are regular languages, then their concatenation $$X\cdot Y = \{xy\mid x\in X, y\in Y\}$$ is regular. This is a standard result that can be found in almost any introduction to regular languages. The idea (it's Theorem 1.4.7 in the linked notes) is to have finite automata $M_X, M_Y$ for languages $X$ and $Y$ and then construct a new FA for $X\cdot Y$ by "gluing" the final states of $M_X$ to the start state of $M_Y$ by $\epsilon$-moves.

The intuition here is that unlike the language $$2A=\{aa \mid a\in A\}$$ where a machine to recognize a word in $2A$ would have to "remember" $a$ and somehow determine that the first half matches the second half, no such burden holds for $A\cdot A$: all a recognizer has to do is nondeterministically guess where the split occurs and then check that the first part of the word is in $A$ and the second part is also in $A$. In this situation, there's no need to remember the first part and then match it to the second.

• Depending on how you go about defining regular languages, this is not even a result: it's by definition (via regular expressions). – Raphael Mar 16 '15 at 21:57
• @Raphael. Of course, but I avoided going in that direction since there was no indication that the OP had seen regular expressions yet. – Rick Decker Mar 17 '15 at 1:33