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

  • $\begingroup$ The details will depend quite a bit on the specific formalism that you’re using for NFAs. $\endgroup$ Commented Nov 15, 2012 at 21:10
  • 1
    $\begingroup$ what do you mean? $\endgroup$
    – DanielY
    Commented Nov 15, 2012 at 21:31
  • $\begingroup$ 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? $\endgroup$ Commented Nov 15, 2012 at 21:35
  • $\begingroup$ edited my question, given there $\endgroup$
    – DanielY
    Commented Nov 15, 2012 at 21:42

1 Answer 1


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$.

  • $\begingroup$ 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? $\endgroup$
    – DanielY
    Commented Nov 15, 2012 at 22:14
  • $\begingroup$ 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$. $\endgroup$ Commented Nov 15, 2012 at 22:18
  • $\begingroup$ so i'll mention it in the proof, as mentioned above. thanks! $\endgroup$
    – DanielY
    Commented Nov 15, 2012 at 22:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .