1
$\begingroup$

I can't understand why do we have to use NFA to prove that concatenation operation is closed. According to sisper's book it says that we can't determine where to split the string, i.e. where to determine that we now have to transition from string of one language to another language. I still don't have a clear understanding of this statement.

$\endgroup$

1 Answer 1

2
$\begingroup$

My only copy of Sipser is the third edition. Here is the relevant quote, after Theorem 26, closure under concatenation of the regular languages.

To prove this theorem, let’s try something along the lines of the proof of the union case. As before, we can start with finite automata $M_1$ and $M_2$ recognizing the regular languages $A_1$ and $A_2$. But now, instead of constructing automaton $M$ to accept its input if either $M_1$ or $M_2$ accept, it must accept if its input can be broken into two pieces, where $M_1$ accepts the first piece and $M_2$ accepts the second piece. The problem is that $M$ doesn’t know where to break its input (i.e., where the first part ends and the second begins). To solve this problem, we introduce a new technique called nondeterminism.

There is not much to add here. To verify that string $w$ is in the concatenation $A_1\cdot A_2$ of two regular languages that are specified by their automata $M_1$ and $M_2$ we have to find a split $w=x\cdot y$ such that $x$ is accepted by $M_1$ and $y$ is accepted by $M_2$. For the first part we simulate $M_1$ for the second $M_2$. As we do not know where to split, nondeterminsim can be employed: at some point in $w$ when we are in a final state of $M_1$ we move to the initial state of $M_2$.

So nondeterminism is a suitable tool. However that does not mean we cannot prove closure under concatenation using deterministic automata. We can use a deterministic simulation, not keeping track of a single split $w=x\cdot y$ that was nondeterministically chosen, but in parallel simulating all those splits. Technically that would mean keeping a set of states of $M_2$ in memory along with a state of $M_1$.

Although possible, this is not a feasible approach for a didactical book: such a proof incorporates the construction that turns a nondeterministic automaton into a deterministic one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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