-3
$\begingroup$

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?

$\endgroup$

marked as duplicate by Juho, David Richerby, D.W., Luke Mathieson, Nicholas Mancuso Mar 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.

  • 2
    $\begingroup$ 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? $\endgroup$ – Raphael Mar 17 '15 at 6:21
  • $\begingroup$ Hint: check the proof for the fact that finite automata and regular expressions define the same set of languages. $\endgroup$ – Raphael Mar 17 '15 at 6:22
5
$\begingroup$

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.

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

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