Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

During an exercise for college, given two NFA's, $A_1\text{ and }A_2$ that accept the languages $L_1\text{ and }L_2$, I've built a NFA, $M$ that accepts the language $L_1*L_2$ (concatenation).

The formal NFA description is: $M = (Q, \Sigma, \delta, q_0, F)$ where

  1. $Q = Q_1 \cup Q_2$
  2. $\Sigma\ $ is the same
  3. $q_0 = q_0\ (\text{of }A_1)$
  4. $F= F\ (\text{of }A_2)$
  5. $\delta = \delta\ (\text{of }A_1)\cup \delta\ (\text{of }A_2)$
  6. and for each state $q \in F\text{ of }L_1, \delta(q,\epsilon)= q_0\text{ of }L_2$

Now I need to formally prove that $L(M) = L(A1) * L(A2)$. Can I get a direction to start from?

Thanks in advance

share|cite|improve this question
The details will depend quite a bit on the specific formalism that you’re using for NFAs. – Brian M. Scott Nov 15 '12 at 21:10
what do you mean? – DanielY Nov 15 '12 at 21:31
You can’t give a formal proof unless you have a formal description of your NFAs. Not everyone uses quite the same formal description. What is yours? – Brian M. Scott Nov 15 '12 at 21:35
edited my question, given there – DanielY Nov 15 '12 at 21:42
up vote 0 down vote accepted

As a hint, a common way of showing two sets, $A\text{ and }B$ are equal is to show that $A\subseteq B$ and that $B\subseteq A$. Depending on your construction of $M$ you shouldn't have much difficulty showing that, first, any word in $L(M)$ is in $L(A_1)*L(A_2)$ and, second, that any word in $L(A_1)*L(A_2)$ is accepted by your $M$.

share|cite|improve this answer
thanks for the quick reply, but I need a point to begin from. The prove in the way you're described it is too straight forward because it implies from the structure of M. How do I prove it formally? – DanielY Nov 15 '12 at 22:14
Begin with "Let $w\in M$, then on $w, M$ will make transitions from its start state to its final state. However, by the construction of $M$ that will require ...". The point is that you can't have a proof that doesn't mention the structure of $M$. – Rick Decker Nov 15 '12 at 22:18
so i'll mention it in the proof, as mentioned above. thanks! – DanielY Nov 15 '12 at 22:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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